力扣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)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。
不允許修改 鏈表。

示例

代碼實(shí)現(xiàn)

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

總結(jié)收獲

很多如果只涉及鏈表中值val規(guī)律的，例如判斷是否是回文鏈表、是否有環(huán)以及找到環(huán)鏈表尾節(jié)點(diǎn)指向的鏈表索引位置等等，都可以通過哈希表方便的做出來。