Linked List Cycle II

今天是一道有關(guān)鏈表的題目，是Linked List Cycle（回復(fù)022查看）的升級版，來自LeetCode，難度為Medium，Acceptance為31.4%。

題目如下

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?

解題思路及代碼見閱讀原文

回復(fù)0000查看更多題目

解題思路

首先，該題是Linked List Cycle（回復(fù)022查看）的升級版。在Linked List Cycle一題中，只需要求是否有環(huán)，比較容易。 只需用兩個(gè)指針，一快一慢，快指針一次走兩步，慢指針一次走一步。

• 若快指針最后指向null，則無環(huán)；
• 若快慢指針最后相遇則有環(huán)。

然后，在該題中要進(jìn)一步求鏈表開始的節(jié)點(diǎn)。這里需要一點(diǎn)數(shù)學(xué)計(jì)算，如圖所示：

鏈表計(jì)算.png

• 首先，設(shè)從鏈表頭到環(huán)開始節(jié)點(diǎn)距離為x；環(huán)的長度為y；從環(huán)開始處到相遇處距離為k；x即為我們要求的距離。
• 第一步，設(shè)快指針與慢指針在5節(jié)點(diǎn)處相遇，則快指針走過x+y+k；慢指針走過x+k。因?yàn)槲覀円阎熘羔樧哌^的長度為慢指針的兩倍，則可得公式1 2(x + k) = x + y + k；
• 第二步，整理公式，得到公式2 x + k = y；
• 第三步，得到公式3 x = y - k即為我們要求的距離。

有了上面的計(jì)算過程，下面我們就可以按照以下思路求該節(jié)點(diǎn)。

• 即當(dāng)快慢指針相遇時(shí)，我們從鏈表頭節(jié)點(diǎn)再定義一個(gè)指針，每次一步向前移動(dòng)，同時(shí)慢指針繼續(xù)每次一步的移動(dòng)。
• 當(dāng)該指針移動(dòng)了x步時(shí)，慢指針此時(shí)也移動(dòng)了x步；
• 而我們已由公式3可知x = y - k，即此時(shí)新的節(jié)點(diǎn)移動(dòng)到了4節(jié)點(diǎn)，慢指針也到了4節(jié)點(diǎn)，兩個(gè)指針在此處相遇。次節(jié)點(diǎn)即為我們要求的節(jié)點(diǎn)。

最后，我們來看代碼。

代碼如下

Java版

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

關(guān)注我
該公眾號會(huì)每天推送常見面試題，包括解題思路是代碼，希望對找工作的同學(xué)有所幫助

image