双指针

21：删除倒数第k个节点

:::info 题目：如果给定一个链表，请问如何删除链表中的倒数第k个节点？假设链表中节点的总数为n，那么1≤k≤n。要求只能遍历链表一次。例如，输入图4.1（a）中的链表，删除倒数第2个节点之后的链表如图4.1（b）所示。 :::

  1. public class Node {
  2.     public Node next;
  3.     public int val;
  5.     public Node(int val) {
  6.         this.val = val;
  7.     }
  8. }
  10. public class DeleteKNodeFromEnd() {
  11.     public void deleteKNodeFromEnd(Node head, int k) {
  12.         // 哨兵节点
  13.         Node dummy = new Node(0);
  14.         dummy.next = head;
  16.         // 定义前后指针
  17.         Node front = dummy;
  18.         Node back = dummy;
  20.         // 先走前指针k步
  21.         for(int i = 0; i < k; i++) {
  22.             front = frone.next;
  23.         }
  25.         // 再同时走前后指针，直到后指针走到最后一个节点
  26.         while(front.next != null) {
  27.             front = front.next;
  28.             back = back.next;
  29.         }
  31.         // 删除back的下一个节点
  32.         back.next = back.next.next;
  34.     }
  35. }

22：链表中环的入口节点

:::info 题目：如果一个链表中包含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点。例如，在如图4.3所示的链表中，环的入口节点是节点3。 :::

  1. /*
  2.  * Ant Group
  3.  * Copyright (c) 2004-2024 All Rights Reserved.
  4.  */
  5. package algorithm.list;
  7. /**
  8.  * @author jiaming
  9.  * @version DetectCycle22.java, v 0.1 2024年02月07日 11:44 jiaming
  10.  */
  11. public class DetectCycle22 {
  13.     // 1. 先写一个辅助函数去找到链表中的环
  14.     // 如果有环，则返回环中的一个node，否则返回null
  15.     private static Node findLoopNode(Node head) {
  17.         if(head == null) {
  18.             return null;
  19.         }
  21.         Node fast = head;
  22.         Node slow = head;
  23.         int countSlowStep = 0;
  24.         while(fast != null && fast.next != null) {
  25.             // 移动快慢指针
  26.             fast = fast.next.next;
  27.             slow = slow.next;
  28.             countSlowStep++;
  30.             // 如果有环，快慢指针终究会相遇（本质上是套圈了）
  31.             if (fast == slow) {
  32.                 return fast;
  34.             }
  35.         }
  37.         // 如果最终退出循环了，且快慢指针没有相遇，那就是没有环，返回null
  38.         return null;
  39.     }
  42.     // 2. 找到环之后，可以确定环的长度k
  43.     // 3. 再利用快慢指针，快指针先走环的长度k；然后快慢指针同时开始走，直到两者相遇，就是入口节点
  44.     public static Node detectCycle(Node head) {
  46.         // 找到环中的一个节点
  47.         Node loopNode = findLoopNode(head);
  49.         // 如果没有环直接退出
  50.         if (loopNode == null) {
  51.             return null;
  52.         }
  54.         // 计算环的长度
  55.         Node p = loopNode.next;
  56.         int loopLength = 1;
  57.         while(p != loopNode) {
  58.             loopLength++;
  59.             p = p.next;
  60.         }
  62.         // 快慢指针找环的入口
  63.         Node fast = head;
  64.         Node slow = head;
  66.         // 快指针先走loopLength
  67.         // 这里解释一下，我们的目标是希望快慢指针在环的入口处相遇，那就是希望慢指针走到环的入口时，快指针刚好已经走完一圈了，那么两者就会相遇
  68.         // 这样的情况下，快指针要比慢指针先多走一圈的长度
  69.         // 其实这里的trick在于，环以外的长度两个指针都是要走的，所以步数差值的0，所以可以不考虑，甚至我们可以假设head就是环的起点
  70.         for (int i = 0; i < loopLength; i++) {
  71.             fast = fast.next;
  72.         }
  74.         // 快慢指针同时走，直到相遇，
  75.         while(fast != slow) {
  76.             fast = fast.next;
  77.             slow = slow.next;
  78.         }
  80.         return fast;
  81.     }
  83.     public static Node detectCycleWithOutLength(Node head) {
  85.         // loopNode为两个快慢指针相遇的节点
  86.         // 此时，慢指针走了k步，快指针走了2k步，两者相差了k步
  87.         // 这 k 步一定是环的长度的整数倍(本质是套圈的逻辑)
  88.         // PS：其实不用考虑环之外的那一截，因为快慢指针都走过，所以不在差值之内
  89.         // 所以2k也是环的长度的整数倍
  90.         Node loopNode = findLoopNode(head);
  92.         if (loopNode == null) {
  93.             return null;
  94.         }
  96.         // 那接下来的思路就是再搞俩快慢指针
  97.         // 快指针就在前面找到的环的一个节点上，慢指针从head开始
  98.         // 此时的关键是，fast比slow多走的k步，k =慢指针走的步数（是环的周长的倍数）
  99.         // 所以当slow走到入口的时候，fast一定也在入口节点
  100.         Node fast = loopNode;
  101.         Node slow = head;
  102.         while (fast != slow) {
  103.             fast = fast.next;
  104.             slow = slow.next;
  105.         }
  107.         return fast;
  108.     }
  110.     public static void main(String[] args) {
  111.         Node one = new Node(1);
  112.         Node two = new Node(2);
  113.         Node three = new Node(3);
  114.         Node four = new Node(4);
  115.         Node five = new Node(5);
  116.         Node six = new Node(6);
  118.         one.next = two;
  119.         two.next = three;
  120.         three.next = four;
  121.         four.next = five;
  122.         five.next = six;
  124.         six.next = three;
  125.         System.out.println("Node=" + detectCycle(one));
  126.         System.out.println("Node=" + detectCycleWithOutLength(one));
  128.         // six.next = one;
  129.         // // System.out.println(detectCycle(one));
  130.         // System.out.println("Node=" + detectCycleWithOutLength(one));
  132.         // six.next = four;
  133.         // // System.out.println(detectCycle(one));
  134.         // System.out.println("Node=" + detectCycleWithOutLength(one));
  137.     }
  138. }

23：两个链表的第1个重合节点‘

:::info 题目：输入两个单向链表，请问如何找出它们的第1个重合节点。例如，图4.5中的两个链表的第1个重合节点的值是4。 :::

image.png

  1. public class IntersectNode{
  2.     public static Node getIntersectNode(Node headA, Node headB) {
  4.         if(headA == null || headB == null) {
  5.             return null;
  6.         }
  8.         int lengthA = getListLength(headA);
  9.         int lengthB = getListLength(headB);
  11.         Head long = lengthA > lengthB ? headA : headB;
  12.         Head short = long == headA ? headB : headA;
  14.         int diff = Math.abd(lengthA - lengthB);
  16.         for(int i = 0; i < diff; i++) {
  17.             long = long.next;
  18.         }
  20.         while(long != short) {
  21.             long = long.next;
  22.             short = short.next;
  23.         }
  25.         return short;
  26.     }
  28.     private static int getListLength(Node head) {
  30.         Node p = head;
  31.         int length = 0;
  32.         while(p != null) {
  33.             length++;
  34.             p = p.next;
  35.         }
  37.         return length;
  38.     }
  39. }

反转链表

24：反转链表

:::info 题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。例如，把图4.8（a）中的链表反转之后得到的链表如图4.8（b）所示。 :::

  1. public class ReverseList {
  2.     public static Node reverseList(Node head) {
  3.         Node pre = null;
  4.         Node cur = head;
  6.         while(cur != null) {
  7.             // 保存下一个节点
  8.             Node next = cur.next;
  9.             // 反转当前节点
  10.             cur.next = pre;
  12.             // 更新cur 和 pre
  13.             pre = cur;
  14.             cur = next;
  15.         }
  17.         // cur 是 null， pre是最后一个节点
  18.         return pre;
  19.     }
  20. }

25：链表中的数字相加

:::info 题目：给定两个表示非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和仍然用单向链表表示？链表中的每个节点表示整数十进制的一位，并且头节点对应整数的最高位数而尾节点对应整数的个位数。例如，在图4.10（a）和图4.10（b）中，两个链表分别表示整数123和531，它们的和为654，对应的链表如图4.10（c）所示。 :::

  1. public class AddTwoNumbers {
  3.     public static Node addTwoNumbers(Node headA, Node headB) {
  5.         // 反转两个链表
  6.         Node x = reverseList(headA);
  7.         Node y = reverseList(headB);
  10.         // 记录新链表的
  11.         Node dummy = new Node(0);
  12.         Node cur = dummy;
  14.         // 从个位数相加
  15.         int carry = 0;
  16.         while(x!=null || y!=null) {
  17.             Node node = new Node;
  19.             int sum = 0;
  21.             if(x != null) {
  22.                 sum += x.val;
  23.             }
  24.             if(y != null) {
  25.                 sum += y.val;
  26.             }
  27.             sum += carry;
  29.             // 计算新的carry
  30.             carry = sum / 10;
  31.             // 计算当前位的值
  32.             node.val = sum%10;
  34.             cur.next = node;
  35.             cur = node;
  36.         }
  38.         if(carry != 0) {
  39.             cur.next = new Node(carry);
  40.         }
  42.         Node newHead = dummy.next;
  43.         return reverseList(newHead);
  44.     }
  45. }

26：重排链表

:::info 问题：给定一个链表，链表中节点的顺序是L0→L1→L2→…→Ln-1→Ln，请问如何重排链表使节点的顺序变成L0→Ln→L1→Ln-1→L2→Ln-2→…？例如，输入图4.12（a）中的链表，重排之后的链表如图4.12（b）所示。 :::

  1. public class reorderList {
  3.     private static Node reorderList(Node head) {
  4.         if(head == null || head.next == null) {
  5.             return head;
  6.         }
  8.         // 找到链表中间节点；
  9.         Node middle = findMiddleNode(head);
  10.         // 将链表分成前后两半，并反转后一半的链表；
  11.         Node secondHalf = middle.next;
  12.         middle.next = null;
  13.         secondHalf = reverseList(secondHalf);
  15.         // 拼接链表
  16.         Node x = head;
  17.         Node y = secondHalf;
  18.         while(x != null && y != null) {
  19.             Node xNext = x.next;
  20.             Node yNext = y.next;
  21.             x.next = y;
  22.             y.next = xNext;
  24.             x = xNext;
  25.             y = yNext;
  26.         }
  28.         return head;
  29.     }
  31.     private static Node reverseList(Node head) {
  33.         if (head == null) {
  34.             return null;
  35.         }
  37.         Node pre = null;
  38.         Node cur = head;
  39.         while(cur != null) {
  40.             // 保存下一个节点
  41.             Node next = cur.next;
  43.             // 反转链表
  44.             cur.next = pre;
  46.             // 更新指针
  47.             pre = cur;
  48.             cur = next;
  50.         }
  52.         return pre;
  53.     }
  55.     private static Node findMiddleNode(Node head) {
  56.         if(head == null) {
  57.             return null;
  58.         }
  60.         Node dummy = new Node(0);
  61.         dummy.next = head;
  62.         Node fast = dummy;
  63.         Node slow = dummy;
  65.         while(fast != null && fast.next !=null) {
  66.             fast = fast.next.next;
  67.             slow = slow.next;
  68.         }
  70.         System.out.println(slow);
  71.         return slow;
  72.     }
  74.     public static void main(String[] args) {
  75.         int[] nums = {1, 2, 3, 4, 5, 6};
  76.         Node head = AlgorithmUtils.constructNode(nums);
  78.         AlgorithmUtils.printListNode(reorderList(head));
  79.     }
  80. }

27：回文链表

:::info 问题：如何判断一个链表是不是回文？要求解法的时间复杂度是O（n），并且不得使用超过O（1）的辅助空间。如果一个链表是回文，那么链表的节点序列从前往后看和从后往前看是相同的。例如，图4.13中的链表的节点序列从前往后看和从后往前看都是1、2、3、3、2、1，因此这是一个回文链表。 :::

  1. public class palindromeList(Node head) {
  3.     public static boolean checkPalindromeList(Node head) {
  4.         if (head == null || head.next == null) {
  5.             return true;
  6.         }
  8.         // 将链表分成前后两半
  9.         Node slow = head;
  10.         Node fast = head.next;
  11.         // 这个循环条件，能让前一半比较短
  12.         while (fast.next != null && fast.next.next != null) {
  13.             fast = fast.next.next;
  14.             slow = slow.next;
  15.         }
  17.         // 如果链表总程度是奇数 fast == null
  18.         Node secondHalf;
  19.         // 如果后一半比较长，说明链表长度是奇数，需要丢弃后一半的第一节点，也就是整个链表的最中间的节点
  20.         if (fast.next != null) {
  21.             // 把最中间的值丢弃
  22.             secondHalf = slow.next.next;
  23.         } else {
  24.             secondHalf = slow.next;
  25.         }
  27.         slow.next = null;
  29.         // 翻转前一半的链表
  30.         head = reverseList(head);
  32.         // 对比两条链表的节点是否一致
  33.         Node x = head;
  34.         Node y = secondHalf;
  35.         while (x != null && y != null) {
  36.             if (x.val != y.val) {
  37.                 return false;
  38.             }
  39.             x = x.next;
  40.             y = y.next;
  41.         }
  43.         return x == null && y == null;
  44.     }
  46.     private Node findMiddleNode(Node head) {
  47.         if (head == null || head.next == null) {
  48.             return head;
  49.         }
  51.         Node dummy = new Node(0);
  52.         dummy.next = head;
  53.         Node fast = dummy;
  54.         Node slow = dummy;
  55.         while (fast != null && fast.next != null) {
  56.             fast = fast.next.next;
  57.             slow = slow.next;
  58.         }
  60.         return slow;
  62.     }
  64.     public static void main(String[] args) {
  65.         int[] nums = {1, 2, 3, 3, 2, 1};
  66.         Node head = AlgorithmUtils.constructNode(nums);
  67.         System.out.println(checkPalindromeList(head));
  69.         int[] nums2 = {1, 2, 3, 2, 1};
  70.         Node head2 = AlgorithmUtils.constructNode(nums2);
  71.         System.out.println(checkPalindromeList(head2));
  73.         int[] nums3 = {1, 2, 3, 4, 2, 1};
  74.         Node head3 = AlgorithmUtils.constructNode(nums3);
  75.         System.out.println(checkPalindromeList(head3));
  76.     }
  77. }

双向链表和循环链表

28：展平多级双向链表

:::info 问题：在一个多级双向链表中，节点除了有两个指针分别指向前后两个节点，还有一个指针指向它的子链表，并且子链表也是一个双向链表，它的节点也有指向子链表的指针。请将这样的多级双向链表展平成普通的双向链表，即所有节点都没有子链表。例如，图4.14（a）所示是一个多级双向链表，它展平之后如图4.14（b）所示。 :::

  1. /**
  2.  * 定义带child的双联表节点
  3.  */
  4. public class ChildNode {
  6.     public ChildNode next;
  8.     public ChildNode pre;
  10.     public ChildNode child;
  13.     public int       val;
  15.     public ChildNode(int val) {
  16.         this.val = val;
  17.     }
  19.     public void link(ChildNode pre, ChildNode next, ChildNode child) {
  20.         this.pre = pre;
  21.         this.next = next;
  22.         this.child = child;
  23.     }
  25.     @Override
  26.     public String toString() {
  27.         return String.valueOf(val);
  28.     }
  29. }
  1. public Flatten {
  3.     public static ChildNode flatten(ChildNode head) {
  4.         flattenGetTail(head);
  5.         return head;
  6.     }
  9.     /**
  10.      * flatten子链表，并返回子链表的尾结点，用于接上当前节点的next
  11.      */
  12.     private static ChildNode flattenGetTail(ChildNode head) {
  13.         if (head == null) {
  14.             return null;
  15.         }
  17.         ChildNode node = head;
  18.         ChildNode tail = null;
  19.         while (node != null) {
  20.             ChildNode next = node.next;
  22.             // 找子节点的tail
  23.             if (node.child != null) {
  24.                 ChildNode child = node.child;
  25.                 // 递归获取子链表的尾结点
  26.                 ChildNode childTail = flattenGetTail(child);
  28.                 // 处理当前节点
  29.                 node.next = node.child;
  30.                 node.child = null;
  32.                 // 处理child节点
  33.                 child.pre = node;
  35.                 // 处理子链表的tail节点
  36.                 childTail.next = next;
  38.                 // 处理next节点
  39.                 if (next != null) {
  40.                     next.pre = childTail;
  41.                 }
  43.                 // 返回子链表的tail
  44.                 tail = childTail;
  45.             } else {
  46.                 // 如果没有子链表，tail就是自己
  47.                 tail = node;
  48.             }
  50.             // 继续处理下一个节点
  51.             node = next;
  52.         }
  54.         return tail;
  55.     }
  57.     public static void main(String[] args) {
  58.         ChildNode one = new ChildNode(1);
  59.         ChildNode two = new ChildNode(2);
  60.         ChildNode three = new ChildNode(3);
  61.         ChildNode four = new ChildNode(4);
  62.         ChildNode five = new ChildNode(5);
  63.         ChildNode six = new ChildNode(6);
  64.         ChildNode seven = new ChildNode(7);
  65.         ChildNode eight = new ChildNode(8);
  66.         ChildNode nine = new ChildNode(9);
  68.         one.link(null, two, null);
  69.         two.link(one, three, five);
  70.         three.link(two, four, null);
  71.         four.link(three, null, null);
  73.         five.link(null, six, null);
  74.         six.link(five, seven, eight);
  75.         seven.link(six, null, null);
  77.         eight.link(null, nine, null);
  78.         nine.link(eight, null, null);
  80.         AlgorithmUtils.printListChildNode(flatten(one));
  81.     }
  82. }

29：排序的循环链表

:::info 问题：在一个循环链表中节点的值递增排序，请设计一个算法在该循环链表中插入节点，并保证插入节点之后的循环链表仍然是排序的。例如，图4.15（a）所示是一个排序的循环链表，插入一个值为4的节点之后的链表如图4.15（b）所示。 :::

  1. public class insert {
  3.     public static Node insert(Node head, Node node) {
  5.         if (head == null) {
  6.             head = node;
  7.             head.next = head;
  8.         } else if (head.next == null) {
  9.             head.next = node;
  10.             node.next = head;
  11.         } else {
  12.             insertCore(head, node);
  13.         }
  15.         return head;
  16.     }
  18.     private static void insertCore(Node head, Node node) {
  20.         Node cur = head;
  21.         Node biggest = head;
  23.         // 循环的条件是前后节点的大小不符合，且还未走一圈回到head
  24.         while (!(cur.val <= node.val && cur.next.val >= node.val) && cur.next != head) {
  25.             cur = cur.next;
  26.             if (cur.val > biggest.val) {
  27.                 biggest = cur;
  28.             }
  29.         }
  31.         if (cur.val <= node.val && cur.next.val >= node.val) {
  32.             Node next = cur.next;
  33.             cur.next = node;
  34.             node.next = next;
  35.         } else {
  36.             node.next = biggest.next;
  37.             biggest.next = node;
  38.         }
  39.     }
  41.     public static void main(String[] args) {
  42.         // int[] nums = {1, 2, 3, 4, 5, 6};
  43.         // Node head = AlgorithmUtils.constructNode(nums);
  44.         //
  45.         // Node tail = head;
  46.         // while(tail.next != null) {
  47.         //     tail = tail.next;
  48.         // }
  49.         // tail.next = head;
  50.         //
  51.         // insert(head, new Node(3));
  52.         // AlgorithmUtils.printListCycleNode(head);
  54.         Node head = null;
  56.         AlgorithmUtils.printListCycleNode(insert(head, new Node(3)));
  58.         // Node head = new Node(4);
  59.         // AlgorithmUtils.printListCycleNode(insert(head, new Node(3)));
  62.         // int[] nums = {1, 2, 3, 4, 5, 6};
  63.         // Node head = AlgorithmUtils.constructNode(nums);
  64.         //
  65.         // Node tail = head;
  66.         // while(tail.next != null) {
  67.         //     tail = tail.next;
  68.         // }
  69.         // tail.next = head;
  70.         //
  71.         // insert(head, new Node(8));
  72.         // AlgorithmUtils.printListCycleNode(head);
  74.     }
  75. }