【函数题】6-1 单链表逆转

1 题目原文

题目链接：6-1 单链表逆转

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

函数接口定义：

List Reverse( List L );

其中 List 结构定义如下：

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

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

裁判测试程序样例：

#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;
}

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

输入样例：

5
1 3 4 5 2

输出样例：

1
2 5 4 3 1

代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB

2 思路解析

一般来说，反转单链表有以下三种类型的思路，虽然每种思路的实现细节可能会演变很多，但是这里只讨论每种思路中的典型实现。

2.1 辅助空间法

    这是最朴素的解法，具体做法如下：
        1. 定义一个辅助空间 tmp，tmp 的典型实现是一个数组，长度与单链表的结点个数相同，也可以是栈（实际还是数组）；
        2. 遍历单链表，在遍历的过程中将单链表的每个结点的值存储到 tmp 中；
        3. 反向读取 tmp 的元素值，同时再遍历单链表，将每个值写回单链表结点中（或者是另外建一个全新的链表）。
    给出伪代码如下：

reverse(A):
	if A == NULL or A.next == NULL
		return A
	tmp = array[(>=A.length)] # 这里表示 tmp 是一个长度大于等于 A 的结点个数的数组
	index = 0
	B = A
	while B != NULL
		tmp[index++] = B.val
		B = B.next
	B = A
	while B != NULL
		B.val = tmp[--index]
		B = B.next
	return A

2.2 递归法

    这是一般不容易想到的解法，“不容易想到”不是指这种解法很困难，而是一般不会往这个方向去想。因为链表这一类题是最简单的问题，按照最容易理解的模拟解法（迭代）就能解决，递归法并不是很合适（而且效率低）。
    单链表可以有一个递归定义：单链表是一个空单链表或者其后继是一个单链表或者空单链表，单个单链表结点也是一个单链表。
    有了这个递归定义，可能会更好理解单链表的递归解法，其具体做法如下：
        1. 如果单链表 L 为空单链表或者只有一个结点，直接返回 L 本身（递归出口）；
        2. 否则，反转 【L 的第一个结点 A】和【反转后的 A 的后继单链表 B】。其中，反转后的逻辑可以通过调用自身实现，即递归。但是如何反转 A 和 B 的问题还需要解决：
        首先考虑 B 是只有一个结点的单链表：此时可能会容易地写出反转它们的逻辑：A.next.next = A; A.next = NULL; return B; 注意反转后的单链表的第一个结点是 B。另外注意到此时 A.next == B，那么可不可以认为 A.next.next = A 等价于 B.next = A 呢？当然不能，这只适合 B 只有一个结点的特殊情况；
        如果 B 有 2 个或者更多个结点呢？此时的 B 还是 A.next 吗？注意 B 的含义是反转后的单链表，由上面反转两个结点的逻辑可以得出：B 的第一个结点是 A 的后继单链表的最后一个结点，即 L 的最后一个结点。而 A.next.next 表示的是 B 的最后一个结点，并且 A.next.next 一定不为空，可以放心调用；
        综上所述，反转逻辑为： A.next.next = A; A.next = NULL; return B;
    给出伪代码如下：

reverse(A):
	# 递归出口
	if A == NULL or A.next == NULL
		return A
	# B 是反转后的 A 的后继单链表
	B = reverse(L.next)
	# 反转 A 和 B: 注意这里的逻辑是反转 A 结点和 B 的最后一个结点，将 A 纳入到 B 中作为最后一个结点，最后合为一个单链表 B
	A.next.next = A
	A.next = NULL
	return B

2.3 迭代法

    这其实是最容易想到的一种解法，并且是很大众的思路：模拟，具体做法如下：
        1. 定义一个新的单链表 H ，初始没有结点；
        2. 定义一个结点指针 P 指向要反转的单链表 L 的第一个结点；
        3. 当 P 没有到达链表尾（P 不为空）时：
            3.1 P 移向直接后继结点；
            3.2 将 L 的第一个结点的后继置为 H；
            3.3 将 H 指向 L；
            3.4 将 L 指向 P，转 3；
    伪代码很容易写出，毕竟是直接模拟的：

reverse(L):
	H = NULL
	P = L
	while P != NULL
		P = P.next
		L.next = H
		H = L
		L = P
	return B

    其实还有很多迭代法的实现，其不同之处就在于指针的多少和转变顺序，大体上没有差别，这里不再赘述。

2.4 小结

    对比以上 3 种解法，有以下结论：

3 代码实现

    有了伪代码之后，代码实现就很容易了，基本就是伪代码稍微翻译一下即可，这里给出 C 语言实现（其实题目只允许使用 C 语言）

3.1 辅助空间法

    请注意：在本题中，这个代码不被接受，可能是其背后的逻辑要求做题者必须会“实际”反转链表而不是投机取巧只反转结点的值。但这仍然是一种解法。

List Reverse(List L) {
    ElementType *tmp = (ElementType *)malloc(100 * sizeof(ElementType));
    int i = 0;
    List p = L;
    while (p) {
        tmp[i++] = p->Data;
        p = p->Next;
    }
    p = L;
    while (p) {
        p->Data = tmp[--i];
        p = p->Next;
    }
    free(tmp);
    return L;
}

3.2 递归法

List Reverse(List L) {
    if (!L || !L->Next) return L;
    List res = Reverse(L->Next);
    L->Next->Next = L;
    L->Next = NULL;
    return res;
}

3.3 迭代法

List Reverse(List L) {
    List res = NULL, p = L;
    while (p) {
        p = p->Next;
        L->Next = res;
        res = L;
        L = p;
    }
    return res;
}

4 总结

    本题是一道很经典的入门题，虽然简单，但是有些细节需要弄清楚之后才能理解透彻。比如使用迭代法反转时，指针的变换顺序，谁先指向谁，怎么形成循环等，以及递归法中如何递归，出口是什么，递归的不变逻辑是什么等。
    解决问题并不是重点，现在网上一搜一大把的题解和代码，重点是思路的形成和构建过程：为什么这样想，代码为什么这样写。本题既可以看作是一道单链表的题，又可以看做是一道训练递归思维的题，相信这篇文章能带给读者一些启发。