LeetCode:Linked List Cycle I & II

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

判斷連結清單是否有環，經典的做法就是設快慢指針各一個，當快指針和慢指針重合時說明連結有環，否則快指針将為null。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
 
public class Solution {
    public boolean hasCycle(ListNode head) {
                if(head==null)return false;
        if(head.next==null)return false;
        ListNode slow=head,fast=head.next;
        while(slow!=fast)
        {
            if(slow==null || fast==null || fast.next==null)return false;
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
    }
}
           

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return 

null

.

這個問題是第一個問題的繼續，如果連結清單有環，快指針”套圈“慢指針時候，快慢指針必然在環上，環的開始節點的特性是必然有兩個不同的node的next指向環的開頭（連結清單不能剛好就是一個環，得有條”尾巴“），慢指針等于快指針的next,以快指針所在Node為标記點（快指針不動），慢指針繼續在環上周遊直至再次遇到快指針，慢指針沒走一次，從頭設定一個p對整個連結進行周遊，如果p!=slow,但是p.next==slow.next;說明其共同的next為環的起點。當滿指針繼續追到快指針的地方，還沒有找到起點，說明整個連結就是一個環，這時候傳回head.

/**
 * 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) {
        if(head==null)return null;
        if(head.next==null)return null;
        if(head.next==head)return head;
        ListNode slow=head,fast=head.next,p;
        while(slow!=fast)
        {
            if(slow==null || fast==null || fast.next==null)return null;
            slow=slow.next;
            fast=fast.next.next;
        }
        slow=fast.next;
       
      while(slow!=fast)
      {     p=head;
            while(p!=fast){
                if(p.next==slow.next && p!=slow)return p.next;
                p=p.next;
            }
           slow=slow.next;
      }
         return head;
      }
    }