給一個(gè)鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)仍源，否則攒岛，輸出null。
解法1:
新建一個(gè)HashSet,遍歷鏈表,每次嘗試添加當(dāng)前遍歷的節(jié)點(diǎn)到HashSet,如果添加失敗,則代表HashSet中已經(jīng)包含該節(jié)點(diǎn),此時(shí)的節(jié)點(diǎn)即為環(huán)的入口點(diǎn).
代碼如下:
public static ListNode solution1(ListNode pHead) {
ListNode node = pHead;
HashSet<ListNode> set = new HashSet<>();
while (node != null) {
if (!set.add(node)) {
return node;
}
node = node.next;
}
return null;
}
因?yàn)轭~外申請(qǐng)了內(nèi)存,所以空間復(fù)雜度為O(n),時(shí)間復(fù)雜度為O(n)
解法2:
- 首先判斷鏈表中是否有環(huán),可以定義兩個(gè)指針,一個(gè)每次走一步,一個(gè)每次走兩步,如果快指針走到鏈表尾部時(shí),兩個(gè)指針沒(méi)有相遇,則代表無(wú)環(huán),否則說(shuō)明又環(huán).
- 確定環(huán)中節(jié)點(diǎn)的個(gè)數(shù)n.
- 將兩個(gè)指針移動(dòng)到鏈頭,一個(gè)先走n步,然后兩個(gè)指針一起走,如果兩個(gè)指針相遇,則相遇點(diǎn)就是環(huán)的入口點(diǎn).
代碼如下:
public static ListNode solution2(ListNode pHead) {
ListNode fast = pHead;
ListNode slow = pHead;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
fast = pHead;
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
此處并沒(méi)有嚴(yán)格按照1,2,3的步驟,因?yàn)榈谝淮蝺蓚€(gè)指針相遇的節(jié)點(diǎn)處,就是3中先走的n步,假設(shè)slow指針走了x步,那么第一次相遇的時(shí)候,fast走了2x步,如果環(huán)中有n個(gè)節(jié)點(diǎn),則fast比slow多走了n步,即2x-n=x,則x=n,所以兩個(gè)指針第一次相遇的節(jié)點(diǎn)就是一個(gè)指針從鏈表頭走了環(huán)中節(jié)點(diǎn)個(gè)數(shù)n步的位置.
這里并沒(méi)有額外申請(qǐng)控件,只是用了兩個(gè)指針變量,所以空間復(fù)雜度為O(1),時(shí)間復(fù)雜度為O(n)
代碼的正確性可以到偶嗌簦客網(wǎng)進(jìn)行驗(yàn)證
