1-2 单链表逆转

分数 4

作者 陈越

单位 浙江大学

本题要求实现一个函数，将给定的单链表逆转。

函数接口定义：

1

List Reverse( List L );

其中List结构定义如下：

1
2
3
4
5
6

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定单链表，函数Reverse要返回被逆转后的链表。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */

List Reverse( List L );

int main()
{
    List L1, L2;
    L1 = Read();
    L2 = Reverse(L1);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

1
2

5
1 3 4 5 2

输出样例：

1
2

1
2 5 4 3 1

我的部分正确

我的是创建新链表，将读取的元素，头插法插入到新表中

这个实现方法是对的，它通过头插法创建了一个新的逆序链表，并返回了这个新链表的头指针 newL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

List Reverse( List L ) {
    // 定义指针p用来遍历L，将元素依次取出
    List p  = L;
    // 依次取出L中的元素，将其头插法插在新链表newL中
    List newL = NULL; // newL指向NULL,当前为空链表
    while (p != NULL) {
        List newNode = (List) malloc(sizeof(struct Node)); // 分配一个新结点
        newNode->Next = newL;
        newL = newNode;
        newNode->Data = p->Data;
        p = p->Next;
    }
    return newL;
}

原因：

没有实现“原地逆转”：虽然你的代码逻辑上是正确的，但它创建了一个全新的链表。在某些判题系统中，对于链表操作题，如果允许的话，可能更倾向于或强制要求使用原地操作。

（更可能的原因）原链表的处理问题：

• 在你的代码中，原链表 L 的结点仍然存在，但是其头指针 L 指向的链表并没有被释放或改变。

• 裁判测试程序样例中：

  1 2 3 4

  L1 = Read(); L2 = Reverse(L1); Print(L1); // 打印 L1 Print(L2); // 打印 L2

• 你的代码逻辑导致 L1 保持不变（因为你只是读取了 L1 的数据，没有修改 L1 的 Next 指针），而 L2 是逆转后的新链表。

• 然而，从输入样例和输出样例来看，判题系统可能期望的是：

  • 原链表 L（即 L1）在被 Reverse 函数调用后被修改为只剩一个头结点（或者被清空/释放，但更可能是只剩一个头结点，以满足Print(L1)的输出）。
  • 返回的新链表 L2 才是逆转后的完整链表。

• 我们看一下样例输出：

  输入样例：5 1 3 4 5 2 (L1 链表数据是 1→3→4→5→2)

  输出样例：

  1 2	1 <-- 对应 Print(L1) 2 5 4 3 1 <-- 对应 Print(L2)

  这个输出暗示：在调用 Reverse(L1) 后，L1 应该只剩下了头结点（数据为 1），而**L2 才是逆转后的整个链表** $(2 \to 5 \to 4 \to 3 \to 1)$。

• 为了满足这种特殊的“分尸”要求，你的头插法实现需要做额外的处理：

  • 在头插法复制数据后，你需要清空原链表 $L$，使其只包含一个结点，并且该结点的数据是你原始链表的第一个元素。

正确答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14

List Reverse(List L) {
    List prev = NULL;    // 前一个节点
    List curr = L;       // 当前节点
    List next = NULL;    // 下一个节点

    while (curr != NULL) {
        next = curr->Next;  // 保存cur的下一个节点
        curr->Next = prev;  // 反转当前节点的指针，改变 curr 的 Next 指针，使其指向 prev (逆转操作)
        prev = curr;        // 移动prev到当前节点
        curr = next;        // 移动curr到下一个节点
    }
    // 反转完成后，prev成为新的头指针
    return prev;
}

• 太妙了

实现了链表的原地反转（不创建新节点，仅通过调整指针方向完成反转）

核心思路：迭代反转指针方向

通过三个指针（prev、curr、next）遍历链表，逐个反转节点的指向，将每个节点的Next从 “指向后一个节点” 改为 “指向前一个节点”，最终完成整个链表的反转。

步骤拆解

1. 初始化指针：

   • prev：指向当前节点的 “前一个节点”，初始为NULL（因为原链表的第一个节点反转后会变成最后一个节点，其Next应为NULL）。
   • curr：指向 “当前正在处理的节点”，初始为原链表的头指针L。
   • next：临时保存当前节点的 “下一个节点”，防止反转指针后丢失原链表的后续节点。

2. 遍历并反转指针（循环执行，直到curr为NULL）：

   • 保存下一个节点：next = curr->Next

     这一步是关键，因为接下来要修改curr->Next，必须先记住原有的下一个节点，否则会丢失链表后续部分。

   • 反转当前节点的指向：curr->Next = prev让当前节点的Next指向它的前一个节点（实现 “反转”）。

   • 移动指针，准备处理下一个节点：

     prev = curr（prev前进到当前节点）

     curr = next（curr前进到下一个节点）。

3. 返回新的头指针：

   当循环结束时，curr为NULL，prev恰好指向原链表的最后一个节点，这个节点就是反转后新链表的头节点，因此返回prev。

示例演示

假设原链表为：1 -> 2 -> 3 -> NULL

• 初始状态：prev=NULL，curr=1，next=?

• 第一次循环：

  next = curr->Next = 2（保存下一个节点 2）

  curr->Next = prev = NULL（1 的 Next 改为 NULL）

  prev = curr = 1，curr = next = 2

  此时链表片段：1 -> NULL，待处理节点：2 -> 3 -> NULL

• 第二次循环：

  next = curr->Next = 3（保存下一个节点 3）

  curr->Next = prev = 1（2 的 Next 改为 1）

  prev = curr = 2，curr = next = 3

  此时链表片段：2 -> 1 -> NULL，待处理节点：3 -> NULL

• 第三次循环：

  next = curr->Next = NULL（保存下一个节点 NULL）

  curr->Next = prev = 2（3 的 Next 改为 2）

  prev = curr = 3，curr = next = NULL

  此时链表片段：3 -> 2 -> 1 -> NULL，循环结束。

• 最终结果：返回prev=3，即反转后的链表为3 -> 2 -> 1 -> NULL。

优点

• 空间效率高：仅使用 3 个额外指针，空间复杂度为O(1)。
• 时间效率高：只需遍历一次链表，时间复杂度为O(n)（n为链表长度）。
• 原地操作：不创建新节点，直接修改原链表的指针，适合不需要保留原链表的场景。

问题解析

一、为什么这个代码会改变原链表，参数不是List L吗，如果是List &L，才会改变啊

在 C 语言中，当参数类型是 List L (即 PtrToNode L) 时，虽然是值传递，但因为它传递的是链表头结点的地址，所以你可以通过这个地址去修改链表的内容（即结点的数据和 Next 指针）。

1. C 语言的值传递

在 C 语言中，所有参数都是值传递 (pass by value)。

• List 的定义：

  1 2	typedef struct Node *PtrToNode; typedef PtrToNode List;

  List L 实际上就是 struct Node *L，它是一个指针变量。

• 调用函数时：

  当你调用 Reverse(L1) 时，系统在函数栈上为 L 复制了一份 L1 的值。这个“值”就是 L1 头结点在内存中的地址。

  变量	类型	存储的值	可修改的内容
  L1 (在 main 中)	List (指针)	0xA000 (头结点地址)	只能通过 L1 = ... 来修改它存储的地址
  L (在 Reverse 中)	List (指针)	0xA000 (头结点地址)	可以通过 L = ... 来修改它存储的地址

2. 为什么能改变原链表？

虽然你在 Reverse 函数内部修改 L 本身（例如 L = L->Next;）只会影响 Reverse 内部的局部变量 L，而不会影响 main 中的 L1。

但是，L 存储的地址 0xA000 允许你访问和修改该地址指向的内存区域，即链表的结点结构。

你的代码 (Reverse 函数) 中，无论是“原地逆转”还是“复制逆转”后的释放，都修改了结点内部的 Next 指针：

• 原地逆转：

  1	current->Next = prev; // current 指向的结点（原链表的一部分）被修改了 Next

  这直接修改了原链表中结点的连接关系，从而改变了原链表。

• 你修改后的“复制逆转”：

  1	L->Next = NULL; // L 指向的第一个结点（原链表的第一个结点）的 Next 被修改为 NULL

  这直接修改了原链表的第一个结点，导致原链表被“截断”，从而改变了原链表。

3. 什么时候需要 List *L 或 C++ 的 List &L？

如果你想在函数内部彻底修改外部指针变量本身（即修改 main 中 L1 所存储的头结点的地址），你就需要传递指针的指针 (List *L) 或者 C++ 的引用 (List &L)。

二、总结对比List L和List &L