代碼隨想錄算法訓(xùn)練四天任務(wù)：
● 24. 兩兩交換鏈表中的節(jié)點(diǎn)
● 19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
● 面試題 02.07. 鏈表相交 （同160）
● 142.環(huán)形鏈表II
● 總結(jié)
24. 兩兩交換鏈表中的節(jié)點(diǎn)
方法一 ：迭代
更直觀的表示：
交換步驟：
結(jié)論
我們要交換兩個(gè)結(jié)點(diǎn)宪巨， 需要保存 兩個(gè)結(jié)點(diǎn)之前的和之后的結(jié)點(diǎn)
因?yàn)殒湵硎菃蜗虻模?那么 之前 結(jié)點(diǎn)我們需要使用一個(gè)臨時(shí)變量保存磷杏。
為什么呢？ 如果當(dāng)前指針遍歷到1結(jié)點(diǎn)捏卓，此時(shí)不保存上一個(gè)結(jié)點(diǎn)极祸，我們就無(wú)法“回頭”找到 它了.之后結(jié)點(diǎn)可以通過(guò) 2->next 得到，只要保證 1->3 連接建立之前怠晴， 2的next值不被改就可以保證鏈表不會(huì)斷遥金。因?yàn)?的next值提前被改了，那么我們就找不到3節(jié)點(diǎn)了蒜田。
基于以上結(jié)論稿械，我們可以給原鏈表加一個(gè)頭結(jié)點(diǎn)，并且定義三個(gè)指針 f/s/t(first/second/third)冲粤，分別指向頭結(jié)點(diǎn)美莫、 第 1 個(gè)結(jié)點(diǎn)页眯、第 2 個(gè)結(jié)點(diǎn)。（在code 中使用了prevNode, swapLeft, swapRight 來(lái)表示）
結(jié)點(diǎn) 1 和 2交換完成之后厢呵， 指針后移2位（代碼層面就是保證不出現(xiàn)空指針異巢鸵穑或者段錯(cuò)誤） ，然后交換 3 和 4 結(jié)點(diǎn)述吸。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode();
dummyNode.next = head;
// prevNode 遍歷鏈表時(shí)用
ListNode prevNode = dummyNode;
while(prevNode.next != null && prevNode.next.next != null){
ListNode swapLeft = prevNode.next; //left node of swap pair
ListNode swapRight = swapLeft.next; //right node of swap pair
ListNode temp = swapRight.next;
//swap
prevNode.next = swapRight;
swapRight.next = swapLeft;
swapLeft.next = temp;
//如果不定義temp變量則swap步驟需改變?yōu)椋? // prevNode.next = swapRight;
// swapLeft.next = swapRight.next;
// swapRight.next = swapLeft;忿族、
//標(biāo)桿位后移2位
prevNode = prevNode.next.next;
}
return dummyNode.next;
}
}
時(shí)間復(fù)雜度： 整個(gè)鏈表需要遍歷一遍，所以算法時(shí)間復(fù)雜度的上限是 O(n)
空間復(fù)雜度： 不管鏈表有多長(zhǎng)蝌矛，運(yùn)行算法需要額外開辟的空間總是常數(shù)級(jí)的道批，算法的空間復(fù)雜度是O(1)
方法二 遞歸
遞歸終止條件： 當(dāng)前節(jié)點(diǎn)或下一節(jié)點(diǎn)為null
class Solution {
public ListNode swapPairs(ListNode head) {
////遞歸的終止條件
if(head == null || head.next == null) return head;
//假設(shè)鏈表是 1->2->3->4
//這句就先保存節(jié)點(diǎn)2
temp = head.next;
//繼續(xù)遞歸，處理節(jié)點(diǎn)3->4
//當(dāng)遞歸結(jié)束返回后入撒，就變成了4->3
//于是head節(jié)點(diǎn)就指向了4隆豹，變成1->4->3
head.next = swapPairs(temp.next);
//將2節(jié)點(diǎn)指向1, 2此時(shí)成為第一個(gè)節(jié)點(diǎn)
temp.next = head;
return temp;
}
}
時(shí)間復(fù)雜度： O(n)
空間復(fù)雜度： 遞歸棧O(n)
19. 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
方法一 2 passes
第一遍循環(huán)找到鏈表長(zhǎng)度len， 得到需要被移除節(jié)點(diǎn)位置
第二遍循環(huán)到節(jié)點(diǎn) , 移除此節(jié)點(diǎn)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode curr = head;
int length = 0;
if(head == null) return head;
//第一遍循環(huán)找到鏈表長(zhǎng)度len茅逮， 得到需要被移除節(jié)點(diǎn)位置 length - n
while(curr != null){
curr = curr.next;
length++;
}
int delPosition = length - n;
//第二遍循環(huán)到delPosition節(jié)點(diǎn), 移除此節(jié)點(diǎn)
curr = dummyHead;
while(delPosition > 0){
curr = curr.next;
delPosition--;
}
curr.next = curr.next.next;
return dummyHead.next;
}
}
時(shí)間復(fù)雜度： 遍歷兩遍 O(n)
空間復(fù)雜度： O(1)
方法二 快慢指針 1 pass
雙指針的經(jīng)典應(yīng)用璃赡，如果要?jiǎng)h除倒數(shù)第n個(gè)節(jié)點(diǎn)，讓fast移動(dòng)n步献雅，然后讓fast和slow同時(shí)移動(dòng)碉考，直到fast指向鏈表末尾。刪掉slow所指向的節(jié)點(diǎn)就可以了挺身。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
//定義fast指針和slow指針侯谁，初始值為虛擬頭結(jié)點(diǎn)
ListNode fast = dummyHead;
ListNode slow = dummyHead;
//fast首先走n + 1步,
//只有這樣同時(shí)移動(dòng)的時(shí)候slow才能指向刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)（方便做刪除操作）
for(int i = 0; i < n + 1; i++){
fast = fast.next;
}
//fast和slow同時(shí)移動(dòng)，直到fast指向末尾
while(fast != null){
fast = fast.next;
slow = slow.next;
}
//刪除slow指向的下一個(gè)節(jié)點(diǎn)
slow.next = slow.next.next;
return dummyHead.next;
}
}
時(shí)間復(fù)雜度： 遍歷一遍 O(n)
空間復(fù)雜度： O(1)
面試題 02.07 鏈表相交 （同160）
給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB 章钾，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)墙贱。如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回 null
方法一 HashSet
思路和算法
判斷兩個(gè)鏈表是否相交贱傀，可以使用哈希集合存儲(chǔ)鏈表節(jié)點(diǎn)惨撇。
首先遍歷鏈表 headA，并將鏈表 headA 中的每個(gè)節(jié)點(diǎn)加入哈希集合中府寒。然后遍歷鏈表 headB魁衙，對(duì)于遍歷到的每個(gè)節(jié)點(diǎn)，判斷該節(jié)點(diǎn)是否在哈希集合中：
如果當(dāng)前節(jié)點(diǎn)不在哈希集合中椰棘，則繼續(xù)遍歷下一個(gè)節(jié)點(diǎn)纺棺；
如果當(dāng)前節(jié)點(diǎn)在哈希集合中榄笙，則后面的節(jié)點(diǎn)都在哈希集合中邪狞，即從當(dāng)前節(jié)點(diǎn)開始的所有節(jié)點(diǎn)都在兩個(gè)鏈表的相交部分，因此在鏈表 headB 中遍歷到的第一個(gè)在哈希集合中的節(jié)點(diǎn)就是兩個(gè)鏈表相交的節(jié)點(diǎn)茅撞，返回該節(jié)點(diǎn)帆卓。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet visited = new HashSet<ListNode>();
ListNode nodeA = headA;
while(nodeA != null){
visited.add(nodeA);
nodeA = nodeA.next;
}
ListNode nodeB = headB;
while(nodeB != null){
if(visited.contains(nodeB)) return nodeB;
nodeB = nodeB.next;
}
//兩個(gè)鏈表不相交巨朦，返回 null
return null;
}
}
時(shí)間復(fù)雜度 O(m + n)
空間復(fù)雜度 O(m) m為鏈表A 長(zhǎng)度
方法二 雙指針
用雙指針將時(shí)間復(fù)雜度降低為O(1)
思路：
走到盡頭見(jiàn)不到你，于是走過(guò)你來(lái)時(shí)的路剑令，等到相遇時(shí)才發(fā)現(xiàn)糊啡，你也走過(guò)我來(lái)時(shí)的路。
如果兩個(gè)鏈表相交吁津，則相交后的長(zhǎng)度相同
設(shè)A的長(zhǎng)度為a+c棚蓄，B的長(zhǎng)度為b+c；其中c為A碍脏、B的公共部分梭依；
若相交，鏈表A： a+c, 鏈表B : b+c. a+c+b+c = b+c+a+c 典尾。則會(huì)在c的起點(diǎn)相遇役拴。若不相交，a +b = b+a 钾埂。因此相遇處是NULL
具體解釋：
假設(shè)headA, headB 長(zhǎng)度分別為m,n河闰。 非公共部分長(zhǎng)度分別為a, b; 公共部分長(zhǎng)度為c
情況一： 相交
如果a=b, 則指針pA,pB會(huì)同時(shí)達(dá)到c,pA = pB = c的開始節(jié)點(diǎn)， 返回相交節(jié)點(diǎn)褥紫；
如果a != b,則pA,pB會(huì)分別遍歷完headA, headB姜性。 然后pA移到headB的頭節(jié)點(diǎn)，pB移到headA的頭節(jié)點(diǎn)髓考， 兩指針繼續(xù)分別移動(dòng)污抬。在pA移動(dòng)了a+c+b次，pB移動(dòng)了b+c+a次后绳军，到達(dá)公共部分c
情況二： 不相交
當(dāng)m=n印机， pA,pB同時(shí)到達(dá)鏈表尾部，同時(shí)為null,返回null
當(dāng)m != n, pA, pB 會(huì)各自遍歷完兩個(gè)headA, headB 兩個(gè)鏈表门驾，pA移動(dòng)m+n次射赛，pB移動(dòng)n+m次，同時(shí)變?yōu)閚ull, 返回null
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//設(shè)A的長(zhǎng)度為a+c奶是，B的長(zhǎng)度為b+c楣责；其中c為A、B的公共部分聂沙；
// 拼接AB秆麸、BA：A+B=a+c+b+c B+A=b+c+a+c；由于a+c+b=b+c+a及汉，
//因此二者必定在c的起始點(diǎn)處相遇
if(headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while(pA != pB){
//遍歷完鏈表headA,再遍歷鏈表headB
pA = (pA == null ? headB : pA.next);
//遍歷完鏈表headB,再遍歷鏈表headA
pB = (pB == null ? headA : pB.next);
}
return pA;
}
}
時(shí)間復(fù)雜度 O(m + n)
空間復(fù)雜度 O(1)
雙指針相似思路：
并求出兩個(gè)鏈表長(zhǎng)度的差值沮趣，然后讓curA移動(dòng)到，和curB 末尾對(duì)齊的位置坷随，
此時(shí)我們就可以比較curA和curB是否相同房铭，如果不相同驻龟，同時(shí)向后移動(dòng)curA和curB，如果遇到curA == curB缸匪，則找到交點(diǎn).否則循環(huán)退出返回空指針翁狐。
142. 環(huán)形鏈表II
題意： 給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)凌蔬。 如果鏈表無(wú)環(huán)露懒，則返回 null。
為了表示給定鏈表中的環(huán)砂心，使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開始）隐锭。 如果 pos 是 -1，則在該鏈表中沒(méi)有環(huán)计贰。
說(shuō)明：不允許修改給定的鏈表钦睡。
方法一： 哈希set
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode pos = head;
Set visited = new HashSet<ListNode>();
while(pos != null){
if(visited.contains(pos)) return pos;
visited.add(pos);
pos = pos.next;
}
return null;
}
}
時(shí)間復(fù)雜度： O(n)
空間復(fù)雜度： O(n)
