LeetCode 206 - 反转链表（Reverse Linked List）

问题描述

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例 1：

1 2	输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

1 2	输入：head = [1,2] 输出：[2,1]

示例 3：

1 2	输入：head = [] 输出：[]

约束条件：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路

反转链表是一个经典问题，有两种主要的解法：迭代法和递归法。

方法一：迭代法

迭代法的核心思想是：遍历链表，将当前节点的 next 指针改为指向前一个节点。由于单链表只能从前往后遍历，我们需要使用额外的指针来记录当前节点的前一个节点和后一个节点。

基本步骤：

初始化三个指针：prev（前一个节点）初始为 nil，curr（当前节点）初始为 head，next（下一个节点）在循环中赋值。
在遍历过程中，我们首先保存当前节点的下一个节点，防止链表断开后无法继续遍历。
将当前节点的 next 指针指向 prev。
将 prev 和 curr 指针向前移动一步。
重复步骤 2-4，直到 curr 指向 nil，表示已经遍历完整个链表。

方法二：递归法

递归法的核心思想是：假设链表后面的部分已经反转完成，我们只需要处理当前节点和子问题的关系。

基本思路：

终止条件：当链表为空或只有一个节点时，反转后的结果就是它本身，直接返回。
递归调用：对除了头节点以外的其他节点进行反转，并得到新的头节点（反转后链表的头）。
处理当前节点：将当前节点的下一个节点的 next 指向当前节点，并将当前节点的 next 设为 nil。
返回新的头节点。

实现细节

递归实现

在递归方法中，关键在于理解子问题的边界和如何处理当前节点与子问题的关系。

当我们递归地反转 head.Next 及其后面的节点时，我们得到了一个新的头节点 newHead，它是原链表的最后一个节点。此时，除了 head 节点外，其他所有节点都已反转完成。我们只需要将 head.Next.Next 指向 head（让原来的下一个节点指向自己），然后将 head.Next 设为 nil（断开原来的连接），就完成了整个链表的反转。

迭代实现

在迭代方法中，我们需要小心处理指针的移动，确保不会丢失链表的任何部分。特别是在反转当前节点的 next 指针之前，我们需要先保存下一个节点的引用。

代码实现

递归解法

/**
 * 递归
 */
func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList(head.Next)

	head.Next.Next = head
	head.Next = nil

	return newHead
}

迭代解法

/**
 * 迭代
 */
func reverseList(head *ListNode) *ListNode {

	if head == nil || head.Next == nil {
		return head
	}

	var cur, prev *ListNode
	prev = head
	cur = head.Next
	prev.Next = nil
	for cur != nil {
		tmp := cur.Next
		cur.Next = prev
		prev = cur
		cur = tmp
	}

	return prev
}

优化建议

对于上述迭代解法，虽然结果是正确的，但有几点可以优化：

初始化指针：标准的做法是将 prev 初始化为 nil，cur 初始化为 head，这样可以更简洁地处理各种情况，包括空链表和只有一个节点的链表。
特殊情况处理：虽然代码中有对 head == nil || head.Next == nil 的特殊情况处理，但使用标准的初始化方式后，这个特殊处理是不必要的，因为迭代过程会自然地处理这些情况。
代码简化：可以将初始化和迭代过程简化，减少不必要的步骤。

优化后的迭代版本如下：

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	curr := head

	for curr != nil {
		next := curr.Next    // 临时保存下一个节点
		curr.Next = prev     // 反转当前节点的指针
		prev = curr          // 移动 prev 指针
		curr = next          // 移动 curr 指针
	}

	return prev  // prev 现在指向新的头节点
}

这个优化版本的特点是：

代码更简洁，逻辑更清晰
不需要特殊处理空链表或单节点链表的情况
变量命名更规范，使用 curr 和 next 更容易理解

复杂度分析

时间复杂度

递归解法：O(n)，其中 n 是链表的长度。我们需要对每个节点调用一次递归函数。
迭代解法：O(n)，其中 n 是链表的长度。我们需要遍历整个链表一次。

空间复杂度

递归解法：O(n)，其中 n 是链表的长度。主要是由于递归调用栈的开销。
迭代解法：O(1)，只需要常数级别的额外空间。

两种方法的比较

方面	递归解法	迭代解法
时间复杂度	O(n)	O(n)
空间复杂度	O(n)	O(1)
优点	代码简洁，思路清晰	空间效率高
缺点	空间开销大，可能栈溢出	代码稍复杂，需要多个指针
推荐度	★★★☆☆	★★★★★

关键收获

指针操作：链表问题的核心是指针操作，需要小心处理指针的移动和更新，避免链表断裂或形成环。
迭代与递归：链表问题通常可以使用迭代和递归两种方式解决，迭代方法通常更高效，而递归方法则更直观。
技巧：
- 使用多个指针（如 prev、curr、next）可以有效地处理链表的反转操作
- 在修改指针前，务必先保存必要的引用，防止链表丢失
- 对于特殊情况（如空链表、单节点链表），可以单独处理或设计算法使其自然包含在一般情况中
空间效率：在实际应用中，通常优先考虑迭代解法，因为它的空间复杂度更低，特别是对于长链表，可以避免递归造成的栈溢出问题。