单链表的创建与反转

题目描述

请编写程序，完成单链表的创建与反转：

1. 从键盘读入若干个整数，当读入 -1 时停止读入；-1 是结束标志，不作为结点插入链表；
2. 用尾插法把读入的整数依次建成一个单链表（先读入的结点在前）；
3. 把这个单链表反转（原来在前的结点变到后面）；
4. 输出反转后链表每个结点的值。

例如读入 1 2 3 4 5 -1 时，建立的链表为 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$，反转后为 $5 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1$，应输出 5 4 3 2 1。

输入格式

输入若干个整数，用空格或换行分隔，最后以 -1 结束。

• 输入的整数个数不超过 1000；
• 除结束标志 -1 外，每个整数 $a_i$ 满足 $1 \leq a_i \leq 10^6$。

输出格式

输出一行，为反转后链表各结点的值，相邻两个数用一个空格分隔，行末不要有多余空格。

若链表为空（第一个数就是 -1），则输出一个空行。

样例 #1

样例输入 #1

1 2 3 4 5 -1

样例输出 #1

5 4 3 2 1

样例解释

建立链表 1 → 2 → 3 → 4 → 5，反转后为 5 → 4 → 3 → 2 → 1，输出 5 4 3 2 1。

样例 #2

样例输入 #2

-1

样例输出 #2

样例解释

第一个数就是结束标志 -1，链表为空，输出一个空行。

样例 #3

样例输入 #3

7 -1

样例输出 #3

7

样例解释

链表中只有一个结点 7，反转后仍然是 7。

数据范围

• $0 \leq n \leq 1000$（链表结点个数）
• $1 \leq a_i \leq 10^6$，$a_i$ 为 int 范围内的正整数
• 结束标志为 $-1$

本题共 10 个测试点，每个测试点 10 分，其中测试点 1~3 为题目给出的样例。

提示

一、结点定义

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

二、尾插法建表

需要两个指针：head 指向第一个结点，tail 指向最后一个结点，初值均为 NULL。

1. 读入一个整数 x，若 x == -1 则停止；
2. 用 new Node 申请一个新结点，存入 x，并把它的 next 置为 NULL；
3. 若 head == NULL（链表还是空的），让 head 和 tail 都指向这个新结点；
4. 否则执行 tail->next = p; tail = p; 把它挂到表尾。

三、反转链表（三指针法）

Node* prev = NULL;
Node* cur = head;
while (cur != NULL) {
    Node* nxt = cur->next;   // 先保存后继，否则改了 next 就找不到了
    cur->next = prev;        // 把当前结点的指针方向反过来
    prev = cur;              // prev 前移
    cur = nxt;               // cur 前移
}
head = prev;                 // 循环结束时 prev 指向原链表的最后一个结点

四、输出

从 head 出发，用 while (p != NULL) 逐个输出 p->data，第一个数前不加空格，其余数前先输出一个空格；循环结束后输出一次换行（链表为空时就只输出换行）。

易错点：

• 输出时要用 p = p->next 移动指针，不能写成 p++；
• 反转时必须先用 nxt 保存后继结点，否则链表会断开；
• -1 只是结束标志，不要把它建成结点，也不要把它输出出来。