作业S1E47 关于单链表的问题

3120781247

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

struct Node
{
        int value;
        struct Node *next;
};

void insertNode(struct Node **head, int value)
{
        struct Node *pre;
        struct Node *cur;
        struct Node *new;
       
        cur = *head;
        pre = NULL;
       
        while (cur != NULL && cur->value < value)
        {
                pre = cur;
                cur = cur->next;
        }
       
        new = (struct Node *)malloc(sizeof(struct Node));
        if (new == NULL)
        {
                printf("内存分配失败！\n");
                exit(1);
        }
        new->value = value;
        new->next = cur;
       
        if (pre == NULL)
        {
                *head = new;
        }
        else
        {
                pre->next = new;
        }
}

void printNode(struct Node *head)
{
        struct Node *cur;
       
        cur = head;
        while (cur != NULL)
        {
                printf("%d ", cur->value);
                cur = cur->next;
        }
        putchar('\n');
}

struct Node *reversed(struct Node *head)
{
        struct Node *pre;
        struct Node *cur;
       
        pre = NULL;
        cur = head;
        while(cur)
        {
                struct Node *next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
        }
       
        return pre;
}

int main(void)
{
        struct Node *head = NULL;
        int input;
       
        printf("\n开始录入数据到单链表a...\n");
        while (1)
        {
                printf("请输入一个整数(输入-1表示结束)：");
                scanf("%d", &input);
                if (input == -1)
                {
                        break;
                }
                insertNode(&head, input);
                printNode(head);
        }
       
        printf("\n下面将单链表a原地反转...\n");
        head = reversed(head);
        printNode(head);
       
        return 0;
}

reversed函数里的 "while(cur)" 这段步骤是怎么样的？最好详细点

ExiaGN001

只要cur不是空（没到链表尾）
那么让node.next->node.next.next
node.next.next->node
相当于调换两元素位置

jackz007

1、链表本来是由头结点开始一个节点指向下一个节点，一直到尾节点；
2、而链表反序操作必须从头结点开始，按照从头到尾的顺序遍历整个链表，所不同的是，需要把本节点的 next 指针由指向下一个节点，改为指向上一个节点，一直到尾节点，从而，原来的头结点成为新的尾节点，原来的尾节点成为新的头结点。

struct Node *reversed(struct Node *head)
{
        struct Node *pre;
        struct Node *cur;
        
        pre = NULL;  // 上一个节点是 NULL
        cur = head;  // 当前节点是头结点 head
        while(cur)   // 只要当前节点不是 NULL 就进入循环
        {
                struct Node * next = cur -> next ;  // 先记住当前节点的 next 指针，因为马上要改写这个指针值，同时，下一个遍历节点就是这个 next；
                cur -> next = pre                ;  // 当前节点 next 指针指向上一个节点            
                pre = cur;                       ;  // 当前节点成为新的上一个节点，准备继续遍历下一个节点
                cur = next;                      ;  // 下一个节点成为新的当前节点
        }
        return pre                               ;  // 到循环结束的时候，cur = NULL，已经没有下一个节点了，那么，最后一个节点 pre 就是新的头结点
}

3120781247

例如
单链表内容为 3 -> 2 -> 1 -> NULL。
第一次循环
next = 2 -> 1 -> NULL (cur->next);
cur->next = NULL (pre); //cur = 3 -> NULL
pre = 3 -> NULL (cur);
cur = 2 -> 1 -> NULL (next);
第二次循环
next = 1 -> NULL (cur->next);
cur->next = 3 -> NULL (pre);  //cur = 2 -> 3 -> NULL
pre = 2 -> 3 -> NULL (cur);
cur = 1 -> NULL (next);
第三次循环
next = NULL (cur->next);
cur->next = 2 -> 3 -> NULL (pre);  //cur = 1 -> 2 -> 3 -> NULL
pre = 1 -> 2 -> 3 -> NULL (cur);
cur = NULL (next);