我想要做的是交换单向链表的第一个和最后一个元素。到目前为止,我有以下代码,我在其中创建了一个列表并向其中添加了一些数字。我的问题出在 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
这是一个演示
这显然是错误的:
*head = (*head)->next;
*head = temp;
这只是用 的值覆盖了先前的值temp
。第一个陈述甚至可能不存在。
你从根本上需要两次交换(技术上一次加上一次分配和终止)
next
指针后者的这些在技术上并不需要,而是直接分配的需要,新的尾部都需要有它的next
设置为空,终止新的列表。
下面显示了一个完整的示例,对其进行了大量评论,希望能够揭示正在发生的事情的算法。
#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
我已经为你留下了清单清理工作(毫无疑问,你已经编写了这样的算法)。这其中的关键是如何使用指向指针的指针来操作链表的指针;不仅仅是一堆临时指针。我强烈建议你在调试器中单步执行交换功能,观察每一步发生的情况。
嗯,你的代码正在运行,它解决了我的问题。但我无法真正理解你在做什么。你能再详细点吗?因为我需要在双向链表和循环链表上做同样的事情。
老实说,我不能。我已经在代码注释和帖子中写了一篇小小说。在此之间,并主动执行我在帖子最后一句中描述的操作(单步调试器并检查变量以准确查看发生了什么),应该足以理解算法。如果没有,您可能需要重新熟悉指针,正如您在代码中看到的,指向指针的指针。
该函数的时间复杂度是多少?它和双向链表和循环链表一样吗?
@user3120283 在单链接单入口(没有尾指针,只有头指针)中交换第一个/最后一个是 O(n);需要顺序扫描(如此处所示)。具有双入口(头指针和尾指针)的双链表是 O(1),因为不需要顺序扫描。循环链表没有第一个/最后一个,所以这个问题在这种情况下有点没有意义。然而,它们通常被实现为双链表,因此,给定一个头指针,之前指向的节点也可以在 O(1) 中交换。