??算法，不如說它是一種思考方式??

算法專欄： ????123

一、??142. 環(huán)形鏈表 II

• 題目描述：給定一個(gè)鏈表的頭節(jié)點(diǎn) head，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。
  如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識鏈表的實(shí)際情況。
  不允許修改 鏈表。

• 來源：力扣（LeetCode）

• 難度：中等

• 提示：
  鏈表中節(jié)點(diǎn)的數(shù)目范圍在范圍 [0, 10⁴] 內(nèi)
  -10⁵ <= Node.val <= 10⁵
  pos 的值為 -1 或者鏈表中的一個(gè)有效索引

• 示例 1：
  
  輸入：head = [3,2,0,-4], pos = 1
  輸出：返回索引為 1 的鏈表節(jié)點(diǎn)
  解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。
  示例 2：
  輸入：head = [1,2], pos = 0
  輸出：返回索引為 0 的鏈表節(jié)點(diǎn)
  解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。
  示例 3：
  輸入：head = [1], pos = -1
  輸出：返回 null
  解釋：鏈表中沒有環(huán)。

• 進(jìn)階：你是否可以使用 O(1) 空間解決此題？

??解題

1.HashSet

HashSet是一種不重復(fù)的集合。
方法就是遍歷鏈表，判斷：集合是否存在這個(gè)節(jié)點(diǎn) || 節(jié)點(diǎn)為空
?① 否：存入集合中。
?② 是：該節(jié)點(diǎn)就是所求。

• code：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> NodeSet=new HashSet<>();
        ListNode p=head;
        while(!NodeSet.contains(p) && p!=null){//節(jié)點(diǎn)判斷是否已經(jīng)被存入（入環(huán)首節(jié)點(diǎn)），或者 no 環(huán)
            NodeSet.add(p);
            p=p.next;
        }
        return p;        
    }
}

2.雙指針

定義兩個(gè)指針：快指針 fast、慢指針 slow。fast 每次走 2 步，slow 每次走 1 步。

1. 相遇
   如果鏈表有環(huán)，那么 fast 和 slow 肯定會相遇；

• 為什么 ？

那么假設(shè)環(huán)長度是 N；
如果 fast 和slow 可以相遇則有：(a + 2 * k) = (b + k) + r * N ；
即：a + k = b + r * N ；對于這樣的方程，取任意a b 可以找到多組解釋，
所以 有環(huán)則必定相遇。
?

2. 找到入環(huán)節(jié)點(diǎn)
   對于相遇的節(jié)點(diǎn) fast=slow，我們在取節(jié)點(diǎn) p指向 head，讓 p 和 slow 同步遍歷，第一次相遇節(jié)點(diǎn)為所求節(jié)點(diǎn)。

• why ？
  

對于fast走到相遇的位置：a + b + n(b + c)；
slow走到相遇的位置：a + b + m(b + c)，其中(m < n)；

而slow每次走的是fast的一半，所以有：2 * [a + b + m(b + c)] = a + b + n(b + c)；
即 a+b = k*(b+c)，
移動(dòng)變形公式：a = r * (b+c) + c ，其中(r=k-1)；
結(jié)合上圖看，從 slow 和 head 同步遍歷，最后在環(huán)的入口相遇。

• code：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head,slow=head;
        while(true){
            if(fast==null||fast.next==null){ //不存在環(huán)，fast當(dāng)然率先 null               
                break;
            }

            fast=fast.next.next;// 2
            slow=slow.next;

            if(fast==slow){// fast、slow 相遇
                fast=head;
                while(fast!=slow){
                    fast=fast.next;
                    slow=slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

空間復(fù)雜度 - O(1)

返回第一頁。?

?物有本末，事有終始，知所先后。??

???????我的CSDN???????? 文章來源地址http://www.zghlxwxcb.cn/news/detail-465710.html

到了這里，關(guān)于LeetCode：142. 環(huán)形鏈表 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！