题目连接

示例

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
示例 1：
image.png
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
image.png
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

解题思路

https://writings.sh/post/data-structure-list-common-algorithm-problems#%E9%93%BE%E8%A1%A8%E6%9F%A5%E7%8E%AF

代码

  1. // 返回环形链表的第一个交叉点
  2. public class leetcode142 {
  3.     // 1。判断是否是环形链表 2。得到交点
  4.     // 哈希表
  5.     // 快慢指针
  7.     public ListNode detectCycle1(ListNode head) {
  8.         ListNode pos = head;
  9.         Set<ListNode> visited = new HashSet<ListNode>();
  10.         while (pos != null) {
  11.             if (visited.contains(pos)) {
  12.                 return pos;
  13.             } else {
  14.                 visited.add(pos);
  15.             }
  16.             pos = pos.next;
  17.         }
  18.         return null;
  19.     }
  22.     public ListNode detectCycle2(ListNode head) {
  23.         if (head == null) return null;
  24.         ListNode slow = head;
  25.         ListNode fast = head;
  26.         while (fast != null){
  27.             slow = slow.next;
  28.             if (fast.next!=null){
  29.                 fast = fast.next.next;
  30.             }else {
  31.                 return null;
  32.             }
  33.             if (fast == slow){
  34.                 ListNode ptr = head;
  35.                 while (ptr != slow){
  36.                     ptr = ptr.next;
  37.                     slow = slow.next;
  38.                 }
  39.                 return ptr;
  40.             }
  41.         }
  42.         return null;
  43.     }
  44. }

这个代码比较清晰

:::info

  1. 定义快慢节点都在头节点处
  2. 循环。退出条件是
    1. 没有环形链表：fast == null || fast.next == null
    2. 有环形链表：slow == fast

当退出循环，并且程序还在运行时，即，出现环形链表，此时快慢双指针都在交点处

  1. 定义一个新节点在头节点处，为了节省空间，将上面的快指针重置到头节点处
  2. 循环。每次移动一个位置，当重置后的快指针移动到交点处时，慢指针已经移动了n-1圈，恰好相遇

时间复杂度 O(N)：第二次相遇中，慢指针须走步数 a空间复杂度 O(1) ：双指针使用常数大小的额外空间。 :::

  1. public ListNode detectCycle(ListNode head) {
  2.         ListNode fast = head, slow = head;
  3.         while (true) {
  4.             if (fast == null || fast.next == null) return null;
  5.             fast = fast.next.next;
  6.             slow = slow.next;
  7.             if (fast == slow) break;
  8.         }
  9.         fast = head;
  10.         while (slow != fast) {
  11.             slow = slow.next;
  12.             fast = fast.next;
  13.         }
  14.         return fast;
  15.     }
  17. 作者：jyd
  18. 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
  19. 来源：力扣（LeetCode）
  20. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。