反转单链表

Question

我知道关于 SO 上的同一个问题有多个问题。但是在某个地方，我无法理解逻辑。

反转链表的函数如下：

void reverse()
{
    struct node *curr=head, *prev=NULL;
    while(curr!=NULL)
    {
        curr->next = prev;
        prev = curr;
        curr = curr->next;
    }
    head = prev;
}

我使用的是全局头指针，链表中节点的结构是：

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

struct node *head = NULL;

这里，每次curr节点都会指向prev节点，最后当curr节点遍历链表时，prev节点将指向我作为头指针的列表中的最后一个节点。

但是，此逻辑不会反转列表，只会打印第一个节点。所以，我认为代码只执行了一次，但我无法发现错误。

使程序完整的其他功能：

#include <stdio.h>
#include <stdlib.h>

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

struct node *head = NULL;

void add(int n)
{
    struct node *temp = (struct node*)malloc(sizeof(struct node));
     temp->data = n;
     temp->next = NULL;
     if(head == NULL)
     {
        head = temp;
        return;
     }
    temp->next = head;
    head = temp;
}

void print()
{
    struct node *temp = head;
     printf("\n The List is : ");
     while(temp!=NULL)
     {
        printf(" %d ",temp->data);
        temp = temp->next;
    }
}

void reverse()
{
    struct node *curr=head, *prev=NULL;
    while(curr!=NULL)
    {
        curr->next = prev;
        prev = curr;
        curr = curr->next;
    }
    head = prev;
}

int main(void)
{
    add(1);
    add(2);
    add(3);
    add(4);
    add(5);
    print();
    reverse();
    print();
    return 0;
}

Answer 1

您正在覆盖 curr->next 指针，该指针随后用于迭代列表。代码应该更像这样：

void reverse()
{
    struct node *curr=head, *prev=NULL;
    struct node *next;
    while(curr!=NULL)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
}

反转单链表

Reversing a Singly Linked List

c

reverse

linked-list