链表高频题目和必备技巧

链表高频题目和必备技巧

1. 链表类题目注意点

1，如果笔试中空间要求不严格，直接使用容器来解决链表问题

2，如果笔试中空间要求严格、或者在面试中面试官强调空间的优化，需要使用额外空间复杂度**O(1)**的方法

3，最常用的技巧-快慢指针

4，链表类题目往往都是很简单的算法问题，核心考察点也并不是算法设计，是coding能力

5，这一类问题除了多写多练没有别的应对方法

注意: 链表类问题既然练的就是coding，那么不要采取空间上讨巧的方式来练习

注意: 链表相关的比较难的问题是约瑟夫环问题，会在之后补充

2. 相关题目

注意：

这些题目往往难度标为“简单”，是因为用容器解决真的很简单

但是不用容器、实现额外空间复杂度O(1)的方法并不轻松，包括很多提交的答案也都没有符合要求

• 题目1 : 返回两个无环链表相交的第一个节点

  • 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/

  • 思路

    • 先判断是否不相交
      • 若有一个为空则不相交
      • 长链表提前走差值个, 随后两链表一同走, 走到尾巴, 若不相同, 则不相交
    • 两链表从头走, 直至寻找到第一个公共节点

  • 代码

    • 	public static ListNode getIntersectionNode(ListNode h1, ListNode h2) {// 1. 先判断是否不相交// 边界: 只要有一个为空就不相交if (h1 == null || h2 == null) {return null;}ListNode a = h1, b = h2;// 计算两个链表长度之差int diff = 0;while (a.next != null) {a = a.next;diff++;}// a来到最后一个结点while (b.next != null) {b = b.next;diff--;}// b来到最后一个结点// 边界: 如果两个链表的尾结点不相等, 则一定不相交if (a != b) {return null;}// 2. 寻找第一个公共结点// 如果长度不等,把长链表给a,短链表给bif (diff >= 0) {a = h1;b = h2;} else {a = h2;b = h1;}// 取差值的绝对值diff = Math.abs(diff);// 长链表先走差值步while (diff-- != 0) {a = a.next;}// 长链表和短链表一起走while (a != b) {a = a.next;b = b.next;}// 当再次相交的时候停止return a;}
      

• 题目2 : 每k个节点一组翻转链表

  • 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/

  • 思路

    • 由于要返回总的头结点, 单独讨论第一组

      • 第一组够不够k个, 不够直接返回head
      • 第一组反转(反转的过程中, lastTeamEnd.next指向下一组的头), 并记录反转后的头,用于返回
      • 反转后记录lastTeamEnd为原来的head(start),

    • 讨论接下来其他组

      • 判断接下来的组够不够k个, 不够直接返回

      • 够了,翻转,调整将上一组的尾连到这一组的头, lastTeamEnd来到这一组的尾

      • 一致循环到没有下一组

  • 代码

    • 	public static ListNode reverseKGroup(ListNode head, int k) {// 1. 先讨论第一组ListNode start = head;// 看第一组够不够k个ListNode end = teamEnd(start, k);if (end == null) {return head;}// 第一组  很特殊因为牵扯到换头的问题head = end;// 反转后头变成尾reverse(start, end);// 在反转的过程中会连上下一组// 翻转之后start变成了上一组的结尾节点ListNode lastTeamEnd = start;// 前一组的头变成了尾// 2. 接下来的其他组while (lastTeamEnd.next != null) {// 下一组还有没有start = lastTeamEnd.next;// 下一组的初头end = teamEnd(start, k);// 下一组的初尾if (end == null) {// 不够return head;// 直到下一组不够k个}reverse(start, end);// 够了,反转lastTeamEnd.next = end;// 上一组的尾巴要连到这一组的end(反转后变成头)lastTeamEnd = start;// 该组变为要调整的下一组的上一组}return head;// 直到没有下一组}// 当前组的开始节点是s，往下数k个找到当前组的结束节点返回public static ListNode teamEnd(ListNode s, int k) {while (--k != 0 && s != null) {// 当前计数s = s.next;// 走向下一个}return s;}// s -> a -> b -> c -> e -> 下一组的开始节点// 上面的链表通过如下的reverse方法调整成 : e -> c -> b -> a -> s -> 下一组的开始节点public static void reverse(ListNode s, ListNode e) {e = e.next;// 先保存下一组的第一个节点ListNode pre = null, cur = s, next = null;while (cur != e) {// 当前节点不是下一组的结点, 反转next = cur.next;cur.next = pre;pre = cur;cur = next;}s.next = e;// 将下一组的结点连在反转后的尾巴上}
      

• 题目3 : 复制带随机指针的链表

  • 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/

  • 思路

    • 将原来的结点每一个都赋值一份放在原节点的后面, 将原节点和现节点串在一起
    • 利用新老节点的关系, 设置每一个新节点的random指针
    • 老链表分离 : 老链表重新连在一起，新链表重新连在一起
    • 返回新链表的头节点

  • 代码

    • 	public static Node copyRandomList(Node head) {// 特殊处理if (head == null) {return null;}// 克隆// 1 -> 2 -> 3 -> ...// 变成 : 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> ...Node cur = head;Node next = null;while (cur != null) {next = cur.next;// 记录下一个cur.next = new Node(cur.val);// 克隆cur.next.next = next;// 原来的下一个接在克隆后的节点上cur = next;// 当前节点走到原来的下一个}// 利用上面新老节点的结构关系，设置每一个新节点的random指针cur = head;Node copy = null;while (cur != null) {next = cur.next.next;// 记录下一个值copy = cur.next;// 记录当前节点的克隆节点copy.random = cur.random != null ? cur.random.next : null;cur = next;}// 新老链表分离 : 老链表重新连在一起，新链表重新连在一起Node ans = head.next;// 记录新链表的头节点cur = head;while (cur != null) {next = cur.next.next;copy = cur.next;cur.next = next;// 原链表恢复原状copy.next = next != null ? next.next : null;cur = next;}// 返回新链表的头节点return ans;}
      

• 题目4 : 判断链表是否是回文结构。这个题的流程设计甚至是考研常用。快慢指针找中点。

  • 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/

  • 思路

    • 利用快慢指针找中点

    • 找到后中点就是slow，从中点开始往后的节点逆序

    • 开始头尾对照,设置临时变量进行处理,以保留原来的结点用于还原链表

    • 把链表调整回原来的样子再返回判断结果

  • 代码

    • 	public static boolean isPalindrome(ListNode head) {// 特例判断if (head == null || head.next == null) {// 没有/只有一个结点return true;}// 1. 快慢指针找中点ListNode slow = head, fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}// fast跳不了// 2. 现在中点就是slow，从中点开始往后的节点逆序// head -> ... -> slow -> ... -> ...ListNode pre = slow;ListNode cur = pre.next;ListNode next = null;pre.next = null;// ! 原来slow.next要先保留,赋值给cur, 随后中点的next要悬空(用于后续翻转时作为判断值)while (cur != null) {next = cur.next;// 以防cur->next改变后后续指针丢失cur.next = pre;pre = cur;cur = next;}// 3. 开始对照,设置临时变量进行处理,以保留原来的结点用于还原链表boolean ans = true;ListNode left = head;ListNode right = pre;// head -> ... -> slow <- ... <- pre// left往右、right往左，每一步比对值是否一样，如果某一步不一样答案就是falsewhile (left != null && right != null) {// 循环至中点的next == null,说明为回文结构if (left.val != right.val) {ans = false;break;// 先不返回, 把链表复原}left = left.next;right = right.next;}// 4. 把链表调整回原来的样子再返回判断结果// head -> ... -> slow <- ... <- pre// pre -> ... -> slowcur = pre.next;pre.next = null;next = null;while (cur != null) {// 中点的next为nullnext = cur.next;cur.next = pre;pre = cur;cur = next;}return ans;}
      

  • 某考研题要求收尾挨个相接也用的同样的方法

• 题目5 : 返回链表的第一个入环节点。快慢指针找中点。

  • 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/

  • 思路

    • 特殊处理
    • 设置双指针, 若f在跳的过程中先走到null, 说明无环, 返回
    • 当fs相遇, f回到头结点, s不变
    • f每次跳一步, s每次跳一步
    • 最后相遇时, 一定是在入环的第一个节点

  • 代码

    • 	public static ListNode detectCycle(ListNode head) {// 特殊处理: 为null, 只有一个结点, 只有两个结点且能到头if (head == null || head.next == null || head.next.next == null) {return null;}// 1. f跳两步 s跳一步ListNode slow = head.next;// 已经排除过特殊情况,直接往下跳ListNode fast = head.next.next;while (slow != fast) {// !!如果f先走到头, 说明没有环if (fast.next == null || fast.next.next == null) {return null;}slow = slow.next;fast = fast.next.next;}// 2. 相遇时, f回到头结点, s保持不变fast = head;// 3. f跳一步 s跳一步while (slow != fast) {slow = slow.next;fast = fast.next;}// 4. 最后相遇时一定是在入环的第一个节点return slow;}
      

• 题目6 : 在链表上排序。要求时间复杂度O(n * log n)，额外空间复杂度O(1)，还要求排序有稳定性。

  • 测试链接 : https://leetcode.cn/problems/sort-list/

  • 思路

    • 计算链表的长度, 用于限制步长
    • 开始按照步长进行排序
      • 先处理第一组,因为排序后很可能要换头
      • 继续处理其他组

  • 代码

    • 	public static ListNode sortList(ListNode head) {// 计算链表的长度, 用于限制步长int n = 0;ListNode cur = head;while (cur != null) {n++;cur = cur.next;}// l1...r1 每组的左部分// l2...r2 每组的右部分// next 下一组的开头// lastTeamEnd 上一组的结尾ListNode l1, r1, l2, r2, next, lastTeamEnd;for (int step = 1; step < n; step <<= 1) {// 进来了,说明step<n,即n>=2// 第一组很特殊，因为要决定整个链表的头，所以单独处理// 找第一组的头尾, 第二组的头尾, 保存剩余链表的头部并将12组分离l1 = head;r1 = findEnd(l1, step);l2 = r1.next;r2 = findEnd(l2, step);next = r2.next;r1.next = null;r2.next = null;merge(l1, r1, l2, r2);head = start;// 临时保存lastTeamEnd = end;// 接下来的其他组while (next != null) {l1 = next;r1 = findEnd(l1, step);l2 = r1.next;if (l2 == null) {// 若l2不存在, 则无需进行合并, 直接停止lastTeamEnd.next = l1;// 尾接头,break不是return,因为要继续外层的循环break;}r2 = findEnd(l2, step);next = r2.next;r1.next = null;// !!!!都是断开r!!!!!!!!!!!!!r2.next = null;merge(l1, r1, l2, r2);lastTeamEnd.next = start;// 将上一组和调整好的这一组链接在一起lastTeamEnd = end;// 这一组的尾变成lastTeamEnd}}return head;}// 包括s在内，往下数k个节点返回// 如果不够，返回最后一个数到的非空节点public static ListNode findEnd(ListNode s, int k) {while (s.next != null && --k != 0) {s = s.next;}return s;}public static ListNode start;public static ListNode end;// l1...r1 -> null : 有序的左部分// l2...r2 -> null : 有序的右部分// 整体merge在一起，保证有序// 并且把全局变量start设置为整体的头，全局变量end设置为整体的尾public static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {ListNode pre;// 找头if (l1.val <= l2.val) {start = l1;pre = l1;l1 = l1.next;} else {start = l2;pre = l2;l2 = l2.next;}// 合并while (l1 != null && l2 != null) {if (l1.val <= l2.val) {pre.next = l1;pre = l1;l1 = l1.next;} else {pre.next = l2;pre = l2;l2 = l2.next;}}// 找尾if (l1 != null) {pre.next = l1;end = r1;} else {pre.next = l2;end = r2;}}