class034 链表高频题目和必备技巧【算法】
code1 160. 相交链表
// 返回两个无环链表相交的第一个节点
// 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
容器法：HashSet记录list1，遍历list2，看是否包含在HashSet中
思路：让长链表先走diff步，短链表之后一起走
package class034; // 返回两个无环链表相交的第一个节点 // 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/ public class Code01_IntersectionOfTwoLinkedLists { // 提交时不要提交这个类 public static class ListNode { public int val; public ListNode next; } // 提交如下的方法 public static ListNode getIntersectionNode(ListNode h1, ListNode h2) { if (h1 == null || h2 == null) { return null; } ListNode a = h1, b = h2; int diff = 0; while (a.next != null) { a = a.next; diff++; } while (b.next != null) { b = b.next; diff--; } if (a != b) { return null; } if (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; } }
code2 25. K 个一组翻转链表
// 每k个节点一组翻转链表
// 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
容器法：放到数组中，swap结点
思路：每次反转k个
package class034; // 每k个节点一组翻转链表 // 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/ public class Code02_ReverseNodesInkGroup { // 不要提交这个类 public static class ListNode { public int val; public ListNode next; } // 提交如下的方法 public static ListNode reverseKGroup(ListNode head, int k) { ListNode start = head; ListNode end = teamEnd(start, k); if (end == null) { return head; } // 第一组很特殊因为牵扯到换头的问题 head = end; reverse(start, end); // 翻转之后start变成了上一组的结尾节点 ListNode lastTeamEnd = start; while (lastTeamEnd.next != null) { start = lastTeamEnd.next; end = teamEnd(start, k); if (end == null) { return head; } reverse(start, end); lastTeamEnd.next = 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; } }
code3 138. 随机链表的复制
// 复制带随机指针的链表
// 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/
容器法：HashMap<原型,克隆>
思路：1把克隆结点插入到原型结点之后 2每两个取出来，设置r指针 3分离链表
package class034; // 复制带随机指针的链表 // 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/ public class Code03_CopyListWithRandomPointer { // 不要提交这个类 public static class Node { public int val; public Node next; public Node random; public Node(int v) { val = v; } } // 提交如下的方法 public static Node copyRandomList(Node head) { if (head == null) { return null; } Node cur = head; Node next = null; // 1 -> 2 -> 3 -> ... // 变成 : 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> ... while (cur != null) { next = cur.next; cur.next = new Node(cur.val); cur.next.next = next; cur = next; } cur = head; Node copy = null; // 利用上面新老节点的结构关系，设置每一个新节点的random指针 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; } }
code4 234. 回文链表
// 判断链表是否是回文结构
// 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/
容器法：数组判断 压栈得到逆序
思路：快慢指针找到链表中点，然后翻转后一半的链表，接着对比左右链表的链表；最后记得还原链表。
考研常考：a1->a8->a2->a7->a3->a6->a4->a5
package class034; // 判断链表是否是回文结构 // 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/ public class Code04_PalindromeLinkedList { // 不要提交这个类 public static class ListNode { public int val; public ListNode next; } // 提交如下的方法 public static boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } ListNode slow = head, fast = head; // 找中点 while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } // 现在中点就是slow，从中点开始往后的节点逆序 ListNode pre = slow; ListNode cur = pre.next; ListNode next = null; pre.next = null; while (cur != null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } // 上面的过程已经把链表调整成从左右两侧往中间指 // head -> ... -> slow <- ... <- pre boolean ans = true; ListNode left = head; ListNode right = pre; // left往右、right往左，每一步比对值是否一样，如果某一步不一样答案就是false while (left != null && right != null) { if (left.val != right.val) { ans = false; break; } left = left.next; right = right.next; } // 本着不坑的原则，把链表调整回原来的样子再返回判断结果 cur = pre.next; pre.next = null; next = null; while (cur != null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } return ans; } }
code5 142. 环形链表 II
// 返回链表的第一个入环节点
// 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/
容器法：HashSet存入遍历到的结点，如果存在被记录过，就是有环，返回被记录的结点
快慢指针：快指针一次走2步，慢指针一次走1步，直到相遇；快指针从起点一次走一步，慢指针从相遇点一次走一步，直到再次相遇，即是第一个入环节点。
package class034; // 返回链表的第一个入环节点 // 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/ public class Code05_LinkedListCycleII { // 不要提交这个类 public static class ListNode { public int val; public ListNode next; } // 提交如下的方法 public static ListNode detectCycle(ListNode head) { if (head == null || head.next == null || head.next.next == null) { return null; } ListNode slow = head.next; ListNode fast = head.next.next; while (slow != fast) { if (fast.next == null || fast.next.next == null) { return null; } slow = slow.next; fast = fast.next.next; } fast = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } }
code6 148. 排序链表
// 排序链表
// 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
// 数组排序做不到，链表排序可以
// 测试链接 : https://leetcode.cn/problems/sort-list/
package class034; // 排序链表 // 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性 // 数组排序做不到，链表排序可以 // 测试链接 : https://leetcode.cn/problems/sort-list/ public class Code06_SortList { // 不要提交这个类 public static class ListNode { public int val; public ListNode next; } // 提交如下的方法 // 时间复杂度O(n*logn)，额外空间复杂度O(1)，有稳定性 // 注意为了额外空间复杂度O(1)，所以不能使用递归 // 因为mergeSort递归需要O(log n)的额外空间 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) { // 第一组很特殊，因为要决定整个链表的头，所以单独处理 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) { lastTeamEnd.next = l1; break; } r2 = findEnd(l2, step); next = r2.next; r1.next = null; r2.next = null; merge(l1, r1, l2, r2); lastTeamEnd.next = start; lastTeamEnd = end; } } 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; } } }
