基础数据结构之链表相关的一些问题
作者：Grey
原文地址：
反转单链表
题目描述见：LeetCode 206. Reverse Linked List
思路如下
对于任何一个节点 cur 来说，记录一个前驱节点 pre (第一个节点的前驱节点是 null )
先用一个临时节点 tmp 记录 cur 的下一个节点，然后设置
cur.next = pre; pre = cur; cur = tmp; 以下是示例图
假设原始链表如下
第一个节点的反转流程如下
第二个节点的反转流程如下
最后返回 pre 节点即为反转后的节点。
代码如下
class Solution { public ListNode reverseList(ListNode cur) { if (cur == null || cur.next == null) { return cur; } ListNode pre = null; while (cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } } 时间复杂度O(N)，空间复杂度O(1)。
反转链表也可以用递归方法来实现
定义递归函数 ListNode reverse(ListNode cur)，这个递归函数的含义是
反转以 cur 为头的链表，并把反转后的头节点返回。
这个递归函数的 base case 是，只有一个节点的时候，即
if (cur == null || cur.next == null) { return cur; } 这种情况下，直接返回当前节点即可。
接下来是普遍情况：
当前来到 cur 节点，c，d，e 已经完成了反转。
此时 cur 需要做如下操作。把 c , d, e 反转后的头节点获取到，假设为 pre ， 在上图中，pre 就是 e 节点，就是反转链表的头节点。然后再做如下操作
cur.next.next = cur; cur.next = null; 
其中cur.next = null非常重要，只有这样，才能防止出现环。完整代码如下
class Solution { public ListNode reverseList(ListNode cur) { return reverse(cur); } // 反转cur为头的链表，并把反转后的头节点返回 public ListNode reverse(ListNode cur) { if (cur == null || cur.next == null) { return cur; } ListNode pre = reverse(cur.next); cur.next.next = cur; cur.next = null; return pre; } } 时间复杂度O(N)
空间复杂度O(N)(递归栈占用的空间)
反转双向链表
双向链表和单链表的反转类似，每个节点要多处理一次每个节点的前驱指针，
完整代码如下
package snippet; import java.util.ArrayList; import java.util.List; // 反转双向链表 public class Code_0008_ReverseDoubleList { public static class DoubleNode { public int value; public DoubleNode last; public DoubleNode next; public DoubleNode(int data) { value = data; } } public static DoubleNode reverseDoubleList(DoubleNode cur) { DoubleNode pre = null; while (cur != null) { DoubleNode tmp = cur.next; cur.next = pre; // 处理前驱指针 cur.last = tmp; pre = cur; cur = tmp; } return pre; } } 反转单链表一部分
题目描述见：LeetCode 92. Reverse Linked List II
本题核心依然是反转链表，只是增加了一些变量来记录需要反转链表的头位置和结尾位置，不过需要注意的是，本题的链表开始位置是从 1 开始，所以，如果m = 1 && n != 1，说明反转链表后需要返回新的头部，只要m > 1，反转链表一部分以后，返回原先的头即可。
完整代码见
class Solution { public static ListNode reverseBetween(ListNode head, int m, int n) { if (m == n) { // 不变 return head; } ListNode startPre = null; ListNode start = null; ListNode end; ListNode endAfter = null; ListNode cur = head; int i = 1; while (i <= n) { if (i == m - 1) { startPre = cur; } else if (i == m) { start = cur; } else if (i == n) { end = cur; if (end.next != null) { endAfter = end.next; end.next = null; } } cur = cur.next; i++; } i = m; ListNode pre = null; // 反转链表操作 while (i <= n) { ListNode tmp = start.next; start.next = pre; pre = start; start = tmp; if (i == m) { pre.next = endAfter; } i++; } if (m == 1 && n != 1) { // 换头了 return pre; } startPre.next = pre; // 返回原来的头节点即可。 return head; } } 在链表中删除指定值的所有节点
题目链接：LeetCode 203. Remove Linked List Elements
主要思路就是遍历链表，找到对应值的元素，就做删除操作，对于普遍位置来说，删除操作可以按如下方式进行
不过，需要注意一个边界条件，就是：如果要删除的节点就是头节点，那么经过删除后，会面临要换头的情况。
所以在一开始的时候，需要做如下判断
while (head != null && head.val == val) { head = head.next; } 即找到第一个不需要删的节点。
完整代码见
class Solution { public static ListNode removeElements(ListNode head, int val) { if (null == head) { return null; } while (head != null && head.val == val) { head = head.next; } if (head == null) { return null; } ListNode c = head; ListNode n = c.next; while (n != null) { if (n.val == val) { c.next = n.next; n = n.next; } else { c = n; n = c.next; } } return head; } } 两个链表相加问题
题目链接见：LeetCode 2. Add Two Numbers
没有特别的算法，就是要注意每次相加可能会有进位的问题，所以设置一个数据结构Node，用于存每一位计算的结果，包括这一位是否有进位的情况。
public static class Node { // 当前值 public int v; // 进位值（只能是0或者1） public int n; } 每次操作相加的方法封装为如下
private static Node add(int v1, int v2) { Node n = new Node(); // 5 + 7 = 12 // 则 当前值为：n.v = 2 // 进位值为：n.n = 1 n.v = (v1 + v2) % 10; n.n = (v1 + v2) / 10; return n; } 还有一个边界条件，由于是从左往右依次相加，所以最右侧如果相加后超过了 9 ，那么需要在最右侧的右侧继续进一位。例如：
.....8 + .....7 = .....51 <--注意得到5以后，还要继续向右侧进1。 完整代码见：
class Solution { public static class Node { // 当前值 public int v; // 进位值（只能是0或者1） public int n; } // l1 和 l2 非空 public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode result = new ListNode(); Node start = add(l1.val, l2.val); result.val = start.v; l1 = l1.next; l2 = l2.next; ListNode c = result; while (l1 != null && l2 != null) { start = add(l1.val + l2.val, start.n); c.next = new ListNode(start.v); c = c.next; l1 = l1.next; l2 = l2.next; } while (l1 != null) { start = add(l1.val, start.n); c.next = new ListNode(start.v); c = c.next; l1 = l1.next; } while (l2 != null) { start = add(l2.val, start.n); c.next = new ListNode(start.v); c = c.next; l2 = l2.next; } if (start.n != 0) { c.next = new ListNode(1); } return result; } private static Node add(int v1, int v2) { Node n = new Node(); n.v = (v1 + v2) % 10; n.n = (v1 + v2) / 10; return n; } } K个节点的组内逆序调整问题
LeetCode 25. Reverse Nodes in k-Group
本题需要设计两个方法：
第一个方法ListNode getKGroupEnd(ListNode start, int k)：从链表 start 位置开始，数够 k 个位置，返回 k 个位置后的那个节点。
比如链表为：
...-> start -> b -> c -> d -> e k = 3 表示从 start 开始，数够 3 个，所以返回 c 节点
如果是下述情况
...-> start -> b -> c -> null k = 6 由于 start 后面不够 6 个，所以返回 null。
public static ListNode getKGroupEnd(ListNode start, int k) { while (--k != 0 && start != null) { start = start.next; } return start; } 第二个方法void reverse(ListNode start, ListNode end)，表示反转 start 到 end 之间的链表。
例如：原链表为：
....->a->b->c->d->e.... 假设start = a, end = d
经过reverse方法，会变成
...d->c->b->a->e..... 有了上述两个方法，我们可以比较方便实现原题要求，主流程如下
public static ListNode reverseKGroup(ListNode head, int k) { ListNode start = head; ListNode end = getKGroupEnd(start, k); if (end == null) { return head; } // 第一组凑齐了！ head = end; reverse(start, end); // 上一组的结尾节点 ListNode lastEnd = start; while (lastEnd.next != null) { start = lastEnd.next; end = getKGroupEnd(start, k); if (end == null) { return head; } reverse(start, end); lastEnd.next = end; lastEnd = start; } return head; } 快慢指针问题
题目描述见：LeetCode 876. Middle of the Linked List
本题主要解决的问题是：
如果一个链表中的节点个数是奇数，则返回中点；如果个数是偶数，则返回下中点。
通常这类问题都是使用快慢指针来做，思路如下
设置一个快指针 fast，一个慢指针 slow， 快指针一次走两步，慢指针一次走一步，快指针走到结尾的时候，慢指针正好到中点位置。
完整代码见：
class Solution { // [1,2,3,4,5] --> 3 // [1,2,3,4,5,6] --> 4 // 奇数返回中点，偶数返回下中点 public static ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } } 快慢指针还可以解决如下类似的问题，只不过是初始化快慢指针的节点有所不同而已。
-
输入链表头节点，奇数长度返回中点，偶数长度返回上中点
-
输入链表头节点，奇数长度返回中点，偶数长度返回下中点
-
输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
-
输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
判断链表是否为回文结构
题目链接为：LeetCode 234. Palindrome Linked List
本题比较好理解的一种解法是使用栈的方式，先将节点全部入栈，然后依次弹出并和原链表一一对比。空间复杂度是O(N)。
// 利用栈O(n) public static boolean isPalindrome(ListNode head) { Stack<ListNode> stack = new Stack<>(); ListNode c = head; while (c != null) { stack.push(c); c = c.next; } c = head; while (c != null) { if (c.val != stack.pop().val) { return false; } c = c.next; } return true; } 本题也可以使用链表操作，将空间复杂度优化为O(1)。
同时本题也需要使用快慢指针找到链表的中间位置，然后中间位置拆分左右两侧的链表来进行比较。整体流程如下图
完整代码见：
class Solution { // 修改原链表，空间O(1) public static boolean isPalindrome(ListNode head) { // 0个节点 // 1个节点 都是回文 if (head == null || head.next == null) { return true; } // 判断两个节点 if (head.next.next == null) { return head.val == head.next.val; } // 判断三个节点 if (head.next.next.next == null) { return head.val == head.next.next.val; } //到这一步，至少有四个节点 // 使用快慢指针 // 奇数来到中点前一个位置(假设为a)和中点后一个位置(假设为b) // 偶数来到上中点位置(假设为a)和下中点位置(假设为b) // head ... a 这个链表，链表反转一下 a...head // 设置两个指针，一个指向a，一个指向b，每个位置对比，结果记录在result中 // 恢复整个链表 ListNode slow = head; ListNode fast = head.next.next; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode a = slow; ListNode b; ListNode mid = null; if (fast != null) { // 链表个数为奇数 mid = a.next; b = a.next.next; } else { b = a.next; // 链表个数为偶数 } // 断开链表 a.next = null; // 反转前半部分链表 ListNode c = reverse(head); boolean result = true; ListNode leftStart = c; ListNode rightStart = b; while (leftStart.next != null) { if (leftStart.val != rightStart.val) { result = false; } leftStart = leftStart.next; rightStart = rightStart.next; } if (leftStart.val != rightStart.val) { result = false; } // leftStart来到开始节点 // rightStart来到末尾节点 ListNode cur = reverse(leftStart); while (cur.next != null) { cur = cur.next; } if (mid == null) { cur.next = b; } else { cur.next = mid; mid.next = b; } return result; } private static ListNode reverse(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } } 合并两个及以上有序链表问题
本文中所有图例见：processon
