956 字
5 分钟
【算法笔记】（十五）链表高频题目和必备技巧
每K个节点一组翻转链表
测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
public ListNode reverseKGroup(ListNode head, int k) { ListNode start = head; ListNode end = endNode(start, k); if (end == null) { return head; } // 第一组很特殊因为牵扯到换头的问题 head = end; reverse(start, end); // 翻转之后start变成了上一组的结尾节点 ListNode lastTeamEnd = start; while (lastTeamEnd.next != null) { start = lastTeamEnd.next; end = endNode(start, k); if (end == null) { return head; } reverse(start, end); lastTeamEnd.next = end; lastTeamEnd = start; } return head; }
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; }
private ListNode endNode(ListNode head, int k) { ListNode end = head; while (-- k != 0 && end != null) { end = end.next; } return end; }随机链表的复试
测试链接：https://leetcode.cn/problems/copy-list-with-random-pointer/
public Node copyRandomList(Node head) { if (head == null) return null; Node node = head; while (node != null) { Node node1 = new Node(node.val); node1.next = node.next; node.next = node1; node = node1.next; } node = head; while (node != null) { if (node.random != null ) node.next.random = node.random.next; node = node.next.next; }
Node result = head.next; node = head; while (node != null) { Node node1 = node.next; node.next = node1.next; if (node1.next != null) node1.next = node1.next.next; node = node.next; } return result; }判断链表是否是回文结构
测试链接：https://leetcode.cn/problems/palindrome-linked-list/
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; }返回链表的第一个入环节点
测试链接：https://leetcode.cn/problems/linked-list-cycle-ii/
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; }排序链表，要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
测试链接：https://leetcode.cn/problems/sort-list/
public static ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; int listLen = 0; ListNode node = head; while (node != null) { listLen ++; node = node.next; } ListNode l1 ,r1 ,l2 ,r2 ,next ,lastEndNode = null; for (int step = 1 ; step < listLen ;step <<= 1) { l1 = head; r1 = endNode(l1 ,step); if (r1.next == null){ break; } l2 = r1.next; r2 = endNode(l2 ,step); next = r2.next; r1.next = null; r2.next = null; merge (l1 ,r1 ,l2 ,r2); lastEndNode = end; head = start; while (next != null) { l1 = next; r1 = endNode(l1 ,step); if (r1.next == null) { lastEndNode.next = l1; break; } l2 = r1.next; r2 = endNode(l2 ,step); next = r2.next; r1.next = null; r2.next = null; merge(l1 ,r1 ,l2 ,r2); lastEndNode.next = start; lastEndNode = end; } } return head; }
public static ListNode start = null ,end = null; private static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) { if (l1.val <= l2.val) { end = l1; start = l1; l1 = l1.next; } else { end = l2; start = l2; l2 = l2.next; } while (l1 != null && l2 != null) { if (l1.val <= l2.val) { end.next = l1; end = l1; l1 = l1.next; } else { end.next = l2; end = l2; l2 = l2.next; } } if (l1 != null) { end.next = l1; } if (l2 != null) { end.next = l2; } while (end.next != null) end = end.next; }
private static ListNode endNode(ListNode l1, int step) { while (l1.next != null && --step != 0) { l1 = l1.next; } return l1; } 【算法笔记】（十五）链表高频题目和必备技巧
http://hgqwd.icu/posts/suanfa15/ 部分信息可能已经过时