我想做的是交换单向链表的第一个和最后一个元素。到目前为止,我有以下代码,我在其中创建了一个列表并向其中添加了一些数字。我的问题出在 swapElements1 函数上。
#include <stdio.h>
#include<stdlib.h>
struct node
{
int number;
struct node *next;
};
void addNodeSingle(struct node **head, int num, int thesi) //Function to insert new node at the beginning or the end of the list, depending on the value of "thesi"
{
if (*head == NULL)
{
struct node *current;
current = (struct node*) malloc (1*sizeof(struct node));
current -> number = num;
current -> next = NULL;
*head = current;
}
else
{
if (thesi == 0)
{
struct node *current;
current = (struct node*) malloc (1*sizeof(struct node));
current -> number = num;
current -> next = *head;
*head = current;
}
else
{
struct node *current, *temp;
current = (struct node*) malloc (1*sizeof(struct node));
current -> number = num;
temp = *head;
while (temp -> next != NULL)
temp = temp -> next;
temp -> next = current;
current -> next = NULL;
}
}
}
void displayList(struct node **head) //Function to display the list
{
struct node *current;
if(*head == NULL)
printf("I lista einai adeia!\n");
else
{
current= *head ;
while(current != NULL)
{
printf("%d ",current -> number);
current = current -> next;
}
}
}
void swapElements1(struct node **head) //(not working)Function to swap first and last element of the list
{
struct node *current, *temp;
current = temp = *head;
while(current != NULL)
{
temp = current;
current = current -> next;
}
*head = (*head)->next;
*head = temp;
current = NULL;
}
int main()
{
struct node *head;
head = NULL;
addNodeSingle(&head,5,1);
addNodeSingle(&head,6,1);
addNodeSingle(&head,2,0);
addNodeSingle(&head,7,0);
addNodeSingle(&head,8,0);
printf("List is: ");
displayList(&head);
swapElements1(&head);
printf("\nNew list is: ");
displayList(&head);
}
我得到的输出是:
列表是:8 7 2 5 6
新列表是:6
我需要的是:
列表是:8 7 2 5 6
新列表是:6 7 2 5 8
这是一个 demo
最佳答案
这显然是错误的:
*head = (*head)->next;
*head = temp;
这只是用 temp
的值覆盖了之前的值。第一条语句甚至可能不存在。
你基本上需要两次交换(技术上是一次加上分配和终止)
- 指向两个节点的指针
- 两个节点的
next
指针
后者在技术上不是必需的,但需要直接分配,并且新尾部需要将其next
设置为null以终止新尾部列表。
下面显示了一个完整的示例,其中包含大量注释,希望能揭示正在发生的事情的算法。
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
void swapFirstAndLast(struct node **head)
{
// don't bother unless we have a list of at least two nodes
if (!*head || !(*head)->next)
return;
// start with the head's next pointer (the second node in the list)
struct node **pp = &(*head)->next;
// walk the pointer-to-pointer down the list, each time grasping
// the next node's "next" pointer address until we reach a node
// whose 'next' is NULL. When that happens, `pp` will hold the
// address of the pointer pointing to the last node in the list
while (*pp && (*pp)->next)
pp = &(*pp)->next;
// swap the pointer held in *head with *pp
struct node *tmp = *head;
*head = *pp;
*pp = tmp;
// save new head's next pointer to be the old head's next
(*head)->next = (*pp)->next;
// and finally, terminate the list.
(*pp)->next = NULL;
}
void print_list(const struct node *head)
{
while (head)
{
printf("%d ", head->data);
head = head->next;
}
fputc('\n', stdout);
}
int main()
{
struct node *head = NULL, **pp = &head;
for (int i=1; i<=5; ++i)
{
*pp = malloc(sizeof **pp);
(*pp)->data = i;
pp = &(*pp)->next;
}
*pp = NULL;
print_list(head);
swapFirstAndLast(&head);
print_list(head);
}
输出
1 2 3 4 5
5 2 3 4 1
我已经为你留下了列表清理(毫无疑问你已经编码了这样的算法)。关键在于如何使用指向指针的指针来操作链表的指针;不仅仅是一堆临时指针。我强烈建议您在调试器中单步执行交换函数,观察沿途的每一步发生了什么。
关于C - 交换单链表中的第一个和最后一个元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40389577/