C：反转链表的问题

Question

我正在编写一个程序来创建一个链表（一个节点），然后反转它。链表包含数据和下一个的地址。

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

首先，我创建链表。

struct node *Insert_value(int dataInput,node* head)
{
    node *new_node=NULL;
    new_node = malloc(sizeof(node));
    new_node -> next = head;
    new_node -> data = dataInput;
    head = new_node;
    return head;
}

之后，我创建了一个打印这些数据的功能。 （我称之为PrintNode）

    while(head!= NULL)
        {
            printf("%d\t",head->data);
            head= head->next;
        }
        printf("\n");
}

最后，创建一个函数来反转链表。

struct node* Reversing(node **head)
{
    node *current, *previous, *first;
    current = previous = first = *head;

    first = first->next->next;
    current = current->next;
    previous ->next = NULL;
    current->next = previous;

    while(first != NULL)
    {
        previous = current;
        current = first;
        first = first -> next;
        previous->next = current;
    }

    return current;
}

这是我的完整计划。

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

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

struct node *Insert_value(int dataInput,node* head);
struct node * Reversing(node **head);
void PrintNode(node *head);

main()
{
    node *head = NULL;
    int i=0,dataInput;
    while(i!=5)
    {
        printf("input your elements: ");
        scanf("%d",&dataInput);
        head = Insert_value(dataInput,head);
        i++;
    }
    PrintNode(head);
    head = Reversing(&head); 
    PrintNode(head);


}               

struct node *Insert_value(int dataInput,node* head)
{
    node *new_node=NULL;
    new_node = malloc(sizeof(node));
    new_node -> next = head;
    new_node -> data = dataInput;
    head = new_node;
    return head;
}

struct node* Reversing(node **head)
{
    node *current, *previous, *first;
    current = previous = first = *head;

    first = first->next->next;
    current = current->next;
    previous ->next = NULL;
    current->next = previous;

    while(first != NULL)
    {
        previous = current;
        current = first;
        first = first -> next;
        previous->next = current;
    }

    return current;
}

void PrintNode(node* head)
{
    while(head!= NULL)
        {
            printf("%d\t",head->data);
            head= head->next;
        }
        printf("\n");
}

经过多次调试后，我知道这些功能都很好。但是，在反向函数之后，head变量的下一个节点的地址为NULL。你能解释一下并给我一些建议吗？

Answer 1

将解决您的问题的一行更改（您可视化有点错误）。

current->next =previous;

代替

previous->next = current;

---

您的代码将爆炸为单个元素链接列表。在函数Reversing()中添加适当的检查。如果有单个元素first->next将是NULL。但你写了first->next->next，如果first->next是NULL，将是未定义的行为。

---

在前面的例子中，您只是在Reversing()中创建一个链接列表，链接保持不变，但head指向最后一个节点。所以它的next是NULL。

Answer 2

修改Reversing，以便在末尾附加新节点。浏览列表时，需要提前保存下一个节点（node *next = current->next）

struct node* Reversing(node **head)
{
    node *current = *head;
    node *reverse = NULL;

    while(current)
    {
        node *next = current->next;

        if(!reverse)
        {
            reverse = current;
            reverse->next = NULL;
        }
        else
        {
            current->next = reverse;
        }
        reverse = current;

        current = next;
    }

    return reverse;
}