每天一道leetcode142-尋找鏈表中環的入口

• 2019 年 10 月 4 日
• 筆記

題目

每天一道leetcode142-尋找鏈表中環的入口 分類：鏈表 中文鏈接： https://leetcode-cn.com/problems/linked-list-cycle-ii/ 英文鏈接 https://leetcode.com/problems/linked-list-cycle-ii/

題目詳述

給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。 說明：不允許修改給定的鏈表。 進階： 你是否可以不用額外空間解決此題？

題目詳解

使用額外空間的思路

• 就是使用一個hashmap，去遍歷一遍鏈表，每遍歷一個鏈表，如果不存在這個節點，那麼就插入hashmap，如果存在，說明這個節點已經插入了，那麼這個節點就是重複的節點，為啥重複了，就是環的入口節點了。

程式碼

/**   * 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) {          HashMap<ListNode,Integer> map = new HashMap<>();          if(head == null || head.next == null)              return null;          while(head != null)          {              if(map.containsKey(head) == false)              {                  map.put(head,1);                  head = head.next;              }else{                  return head;              }          }          return null;      }  }  

程式碼講解

• 15-22行，hashmap判斷這個節點如果不存在，那麼插入到hashmap裡面；
• 23-24行，hashmap中存在這個節點，那麼就返回這個節點，也就是入口節點

不使用額外空間的思路

• 使用快慢指針，快指針每次走兩步，慢指針每次走一步，如果快慢指針相遇說明有環；
• 有環以後，需要尋找環入口節點，已經找到了一個環的中的節點，利用這個節點，去往下遍歷，由於是環，所以這個節點肯定會和自身相遇，相遇以後，記錄相遇過程中走的步數，就是環的長度
• 知道環的長度以後，然後再利用快慢指針的思想，快指針先走環長度，然後快慢指針再一起走，這樣因為快指針先走了環的長度，當兩者相遇肯定是環的入口節點相遇（為啥呢，因為快慢指針肯定會進入環裡面，而由於快指針先走了環的長度，所以也就是一個周期，所以只要進入環，那麼這兩個指針必然相遇）

程式碼

/**   * Definition for singly-linked list.   * class ListNode {   *     int val;   *     ListNode next;   *     ListNode(int x) {   *         val = x;   *         next = null;   *     }   * }   */  public class Solution {      boolean flag = true;      public ListNode detectCycle(ListNode head)      {          ListNode pHead = head;          if(pHead == null || pHead.next == null)              return null;          ListNode pNode = judgeHasChain(pHead);          if(pNode != null)          {              int lengthChain = 1;              ListNode pNodeCopy = pNode.next;              while(pNodeCopy != pNode)              {                  lengthChain++;                  pNodeCopy = pNodeCopy.next;              }              ListNode fast = pHead;              ListNode slow = pHead;              int temp = 0;              while(temp < lengthChain)              {                  fast = fast.next;                  temp++;              }              while(fast != slow)              {                  fast = fast.next;                  slow = slow.next;              }              return fast;          }          return null;      }      private ListNode judgeHasChain(ListNode pHead)      {          ListNode fast = pHead.next;          ListNode slow = pHead;          while(fast != slow)          {              if(fast != null && fast.next != null)              {                  fast = fast.next;              }else{                  flag = false;                  break;              }              if(slow != null && slow.next != null)              {                  slow = slow.next;              }else{                  flag = false;                  break;              }              if(fast == slow)              {                  return fast;              }else{                  fast = fast.next;              }          }          if(flag)              return fast;          return null;      }  }  

程式碼講解

• 46-76 就是判斷鏈表中是否有環，之前有詳細講過 之前的文章鏈表：每天一道leetcode141-環形鏈表
• 19行中，如果鏈表有環，那麼返回的這個節點必然在環中
• 22-28行，利用19行的節點，遍歷計算環的長度
• 32-36行，快指針先走環長度
• 37-41行 快慢指針一起走，相遇就是環的入口節點