C - 交换单链表中的第一个和最后一个元素

Question

我想做的是交换单向链表的第一个和最后一个元素。到目前为止，我有以下代码，我在其中创建了一个列表并向其中添加了一些数字。我的问题出在 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

Answer 1

这显然是错误的：

*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

我已经为你留下了列表清理（毫无疑问你已经编写了这样的算法）。关键在于如何使用指向指针的指针来操作链表的指针；不仅仅是一堆临时指针。我强烈建议您 single-step 通过调试器中的交换函数，观察过程中每一步发生的情况。

Answer 2

WhozCraig 的回答已经很完美了，但也许您可能希望查看自己的代码并进行一些调整。基本上，我所做的是在一次迭代之前停止对最后一个元素的搜索，这样 temp 就会停止在 5，current 会停止在 6。此外，你必须使用指针进行四次更改，就像 WhozCraig 所做的那样。这是您的代码，稍作修改：

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->next != NULL)
    {
        temp = current;
        current = current -> next;
    }
    temp->next = *head;
    current->next = (*head)->next;
    (*head)->next = NULL;
    *head = current;
}

这在我的机器上有效。我将您的 while 循环条件从 current 更改为 current->next 并做出了正确的 "pointer changes"。这些指针变化很难解释，通常我先写在纸上，然后写在代码中。

Answer 3

已经有人回答正确了，如果大家有遇到双指针问题的，请参考下面的回答。

void swap(){
if (!head || !(head -> next)){
    return;
}
node* tail = head;
while(tail -> next -> next != NULL){
    tail = tail -> next;
}
node* tmp = head;
head = tail -> next;
tail -> next = tmp;
head -> next = tmp -> next;
tmp -> next = NULL;
return;
}

我已经将头指针声明为全局变量（这就是为什么我不需要在函数内部使用双指针）。

下面是我的结构定义，供大家参考

typedef struct node{
int data;
struct node *next;
}node;

C - 交换单链表中的第一个和最后一个元素

C - Swap first and last element in singly linked list

c

swap

singly-linked-list