LeetCode--142. Linked List Cycle II

蔚落 2022-08-21 00:06 19阅读 0赞

Problem:

> Given a linked list, return the node where the cycle begins. If there is no cycle, return null.  
> Note: Do not modify the linked list.  
> Follow up:  
> Can you solve it without using extra space?

Analysis:  
按I的思路，我们又慢指针S和快指针F。。。F走两步，S走一步。。。若有环，必定相遇。

F走的路程应该是S的两倍

S = x + y
    F = x + y + z + y = x + 2y + z
    2*S = F
    2x+2y = x + 2y + z
    得到x = z

也就是从head到环开始的路程 ＝ 从相遇到环开始的路程

那么。。。只要S和F相遇了，我们拿一个从头开始走，一个从相遇的地方开始走两个都走一步，那么再次相遇必定是环的开始节点。

/*
      * #->#->#->O->#->#->...->#
      *          ^             |
      *          |     环      |
      *          |             |
      *          #<-...<-*<-#<-
      *O为环的起点，*为快指针追上慢指针的节点
      */

Answer:

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    
    public class Solution {
        
        public ListNode detectCycle(ListNode head) {
            //判断链表节点数<=3的情况，因为后面的程序要求节点数大于等于3
            if(head==null || head.next==null) return null;
            if(head.next.next==null) {
                if(head==head.next.next) return head;
                else return null;
            }
            //定义快慢指针，如果存在环，结果会使快指针追上慢指针
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null && fast.next !=null ){
                fast = fast.next.next;
                slow = slow.next;
                if(fast==slow) break;
            }
            //如果while是因为遇到链表尾即没有环 则返回null；
            if(fast==null || fast.next ==null) return null;
            //如果有环则从head再次出发一个节点（速度和slow一样），
            //这个节点和slow相遇的节点即为环的开始点
            else{
                ListNode trird = head;
                while(trird!=slow){
                    trird = trird.next;
                    slow = slow.next;
                }
                return trird;
            }
        }
    }