142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
复杂度分析

  • 时间复杂度：O(N)O(N)，其中 NN 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。
  • 空间复杂度：O(N)O(N)，其中 NN 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。
    1. //哈希表法，空间换时间思路，时间复杂度On,空间复杂度On（整个链表节点 存进hash值）
    2. func detectCycle(head *ListNode) *ListNode {    //。。返回值不是bool值，而是链表形式
    3.   hash := make(map[*ListNode]int)             //建立哈希表，make结构体，map类型，链表形式，返回int
    4.                                               //hash表的作用是，记录该节点是否被遍历，记录该节点的索引为hash值
    5.   for head != nil {
    6.       if _,ok := hash[head]; ok {             //判断索引存在的模板
    7.           return head                            //。。true变为实际头节点
    8.       }
    9.       hash[head] = head.Val                   //建立索引，记录值val
    10.       head = head.Next
    11.   }
    12.   return nil                                    //..返回空，不存在环形
    13. }

image.png
image.png
参考：
相遇时：

  • slow走过的路程：x + y + n(y+z), n代表slow绕了n圈
  • fast走过的路程：x + y + m(y+z)，m代表fast饶了m圈
  • m > n

因为fast速度是slow两倍：

  • 2(x + y + n(y + z)) = x + y + m(y + z)
  • x + y = (m - 2n)(y + z)
  • x = (m - 2n)(y + z) - y
  • y + z就是1圈，假设 o = m-2n，o是一个正整数，那么 x = o(y + z) -y
  • 如果o = 1，那么 x = z，和答主假设的情况一样
  • 如果o > 1，那么 x = (o-1)(y+z) + y + z - y, x = (o-1)(y+z) + z，即x的长度为o-1圈加上z

所以，从第一阶段获得的相遇点，走过x距离机会到达环的起点。
夹逼准则：n是正整数，n<2，所以这里的n就是1，因为快指针每次走两步，慢指针每次走一步，那么相遇时，慢指针在环中不会走满一圈，而快指针走了一圈多但不到两圈。

//双指针法
func detectCycle(head *ListNode) *ListNode {
    if head ==nil || head.Next ==nil {
        return nil
    }   //1.排除【】为空，为1的情况

    slow, fast := head, head
    for fast && fast.Next != nil !=nil {
        slow =slow.Next
        fast =fast.Next.Next    //3.快慢指针 前进规则 下一跳

        if fast == slow {   //理论推导a=c时，两者重逢，a+T(b+c)
            tmp := head     //4.建立新指针tmp走一格
            for tmp != slow {   //两者没相遇，就继续走，知道相遇
                tmp = tmp.Next
                slow = slow.Next
            }
            return tmp      //相遇点就是要求的a点
        }

    }
    return nil
}

image.png