環(huán)形鏈表 Ⅱ【LC142】

給定一個(gè)鏈表，返回鏈表開始入環(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í)鏈表的實(shí)際情況。

不允許修改 鏈表。

作者：力扣 (LeetCode)
鏈接：https://leetcode-cn.com/leetbook/read/linked-list/jjhf6/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

哈希表

• 思路：使用哈希表存放鏈表中的節(jié)點(diǎn)，找到第一個(gè)在哈希表中重復(fù)出現(xiàn)的結(jié)點(diǎn)，即為環(huán)的入口

• 2021/12/9

  /**
   * 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) {
          Set<ListNode> seen = new HashSet<>();  
          while(head!=null){
              if(!seen.add(head)){
                  return head;
              }
              head = head.next;
          }
          return null;      
      }
  }
  

• 復(fù)雜度分析

  • 時(shí)間復(fù)雜度：$O(N)$，其中 $N$是鏈表中的節(jié)點(diǎn)數(shù)。
  • 空間復(fù)雜度：$O(N)$

快慢指針

• 2023/07/30

• 思路：

  • 首先，由LC141可知，如果鏈表中存在環(huán)，那么快慢指針會(huì)在環(huán)中相遇，但相遇的位置不一定是入環(huán)口，如下圖所示。設(shè)鏈表中環(huán)外部分的長度為a，慢指針進(jìn)入環(huán)后，又走了b的距離與快指針相遇。此時(shí)，快指針已經(jīng)走完了環(huán)的n圈，因此快指針走過的總距離為$$a+n(b+c)+b$$。

  • 由任意時(shí)刻，快指針走過的距離都為慢指針的2倍。因此，有
    $$a+(n+1)b+nc=2(a+b)??>a=c+(n?1)(b+c)$$

  • 可得從相遇點(diǎn)到入環(huán)點(diǎn)的距離加上n-1圈的環(huán)長，恰好等于從鏈表頭部到入環(huán)點(diǎn)的距離。

  • 因此，當(dāng)快慢指針相遇時(shí)，再額外用一個(gè)指針指向鏈表頭部，隨后，它和慢指針每次向后移動(dòng)一個(gè)位置。最終，它們會(huì)在入環(huán)點(diǎn)相遇。

• 為什么慢指針入環(huán)第一圈沒走完的時(shí)候就會(huì)和快指針相遇？

  1. 首先，快指針先進(jìn)入環(huán)
  2. 當(dāng)慢指針剛到達(dá)環(huán)的入口時(shí)，快指針此時(shí)在環(huán)中的某個(gè)位置（此時(shí)也可能相遇）
  3. 假設(shè)此時(shí)快慢指針的距離為x，若在步驟2相遇，則x=0
  4. 設(shè)環(huán)的周長為n，那么看成快指針追趕慢指針，需要追趕n-x個(gè)單位
  5. 快指針每次都追趕慢指針1個(gè)單位，那么慢指針走了n-x個(gè)單位，又因?yàn)閤>0，則慢指針走的路程小于等于n，因此慢指針走不完一圈就會(huì)與快指針相遇

• 代碼

  public class Solution {
      public ListNode detectCycle(ListNode head) {
          ListNode slowNode = head;
          ListNode fastNode = head;
          while (fastNode != null && fastNode.next != null){
              slowNode = slowNode.next;
              fastNode = fastNode.next.next;
              if (slowNode == fastNode){
                  ListNode curNode = head;
                  while (curNode != fastNode ){
                      curNode = curNode.next;
                      fastNode = fastNode.next;
                  }
                  return curNode;
              }
          }
          
          return null;
      }
  }
  

• 復(fù)雜度分析文章來源地址http://www.zghlxwxcb.cn/news/detail-617208.html

  • 時(shí)間復(fù)雜度：$O(N)$，其中 $N$是鏈表中的節(jié)點(diǎn)數(shù)。
  • 空間復(fù)雜度：$O(1)$

到了這里，關(guān)于【每日一題Day281】LC142鏈表 Ⅱ| 快慢指針 哈希表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！