链表反转操作经典问题详解

1. 反转链表

1.1 问题描述

给定单链表的头节点 head，要求反转链表，并返回新的头节点。
示例：
输入：1 → 2 → 3 → 4 → 5
输出：5 → 4 → 3 → 2 → 1

---

1.2 方法思路

迭代法

1. 双指针法：使用 prev 和 curr 两个指针，逐步反转指针方向。
2. 终止条件：当 curr 遍历到链表末尾时停止。

递归法

1. 递归到末尾：从链表尾部开始反转。
2. 回溯反转：每次回溯时，让后驱节点指向前驱节点。

---

1.3 代码实现

迭代法（Java）

public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;  // 保存下一个节点curr.next = prev;           // 反转指针prev = curr;                // prev前移curr = next;                // curr前移}return prev;  // 新头节点
}

递归法（Java）

public ListNode reverseList(ListNode head) {if (head == null || head.next == null) return head;ListNode newHead = reverseList(head.next);head.next.next = head;  // 后驱节点指向前驱head.next = null;       // 断开原指针return newHead;
}

---

1.4 复杂度分析

方法	时间复杂度	空间复杂度
迭代法	O(n)	O(1)
递归法	O(n)	O(n)

---

1.5 关键点解释

• 迭代法核心：通过 prev 和 curr 的逐步移动，实现指针方向的反转。
• 递归法核心：利用递归栈回溯的特性，从链表尾部开始反转。

---

2. 回文链表

2.1 问题描述

判断单链表是否为回文结构（正序与逆序相同）。
示例：
输入：1 → 2 → 3 → 2 → 1 → 输出：true
输入：1 → 2 → 3 → 4 → 输出：false

---

2.2 方法思路

1. 快慢指针找中点：快指针走两步，慢指针走一步。
2. 反转后半链表：从中点开始反转后半部分链表。
3. 双指针比较：比较前半部分和反转后的后半部分是否一致。

---

2.3 代码实现（Java）

public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) return true;// 1. 快慢指针找中点ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 处理奇数长度链表if (fast != null) slow = slow.next;// 2. 反转后半链表ListNode reversed = reverseList(slow);// 3. 比较两部分ListNode p1 = head, p2 = reversed;while (p2 != null) {if (p1.val != p2.val) return false;p1 = p1.next;p2 = p2.next;}return true;
}// 反转链表辅助函数（迭代法）
private ListNode reverseList(ListNode head) {ListNode prev = null, curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;
}

---

2.4 复杂度分析

• 时间复杂度：O(n)
  找中点（O(n/2)）+ 反转后半（O(n/2)）+ 比较（O(n/2)）= O(n)
• 空间复杂度：O(1)

---

2.5 优化思路

• 避免破坏原链表：比较完成后，可以再次反转后半链表恢复原结构（需增加一次反转操作）。

---

3. 反转链表II（区间反转）

3.1 问题描述

反转链表中从位置 m 到 n 的子链表（区间从1开始计数）。
示例：
输入：1 → 2 → 3 → 4 → 5，m=2，n=4 → 输出：1 → 4 → 3 → 2 → 5

---

3.2 方法思路

1. 哑节点（Dummy Node）：简化头节点可能被反转的边界处理。
2. 定位前驱节点：找到第 m-1 个节点 preM。
3. 反转子链表：反转 m 到 n 的节点，重新连接链表。

---

3.3 代码实现（Java）

public ListNode reverseBetween(ListNode head, int m, int n) {if (head == null || m == n) return head;ListNode dummy = new ListNode(0);  // 哑节点处理边界dummy.next = head;ListNode preM = dummy;// 定位到第 m-1 个节点for (int i = 0; i < m - 1; i++) {preM = preM.next;}// 反转 m 到 n 的节点ListNode start = preM.next;  // 子链表头ListNode curr = start;ListNode prev = null;for (int i = 0; i < n - m + 1; i++) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}// 重新连接链表preM.next = prev;    // 前驱连接新头start.next = curr;   // 原子链表尾连接剩余节点return dummy.next;
}

---

3.4 复杂度分析

• 时间复杂度：O(n)
  定位前驱节点（O(m)）+ 反转子链表（O(n-m+1)）= O(n)
• 空间复杂度：O(1)

---

3.5 边界处理

• 当 m=1 时：哑节点保证 preM 存在，无需特殊处理。
• 当 m=n 时：直接返回原链表。

---

4. 总结

1. 反转链表：迭代法（O(1) 空间）和递归法（O(n) 空间）各有适用场景。
2. 回文链表：结合快慢指针和反转链表，实现 O(1) 空间复杂度。
3. 区间反转：通过哑节点和精准定位，高效处理子链表反转。

核心技巧：

• 双指针法（快慢指针、前后指针）
• 哑节点简化边界条件
• 递归与回溯的灵活应用

通过练习这些经典问题，可以深入掌握链表操作的核心逻辑！