代碼隨想錄算法訓練四天任務：
● 24. 兩兩交換鏈表中的節(jié)點
● 19.刪除鏈表的倒數(shù)第N個節(jié)點
● 面試題 02.07. 鏈表相交 （同160）
● 142.環(huán)形鏈表II
● 總結
24. 兩兩交換鏈表中的節(jié)點
方法一 ：迭代
更直觀的表示：
交換步驟：
結論
我們要交換兩個結點， 需要保存 兩個結點之前的和之后的結點
因為鏈表是單向的， 那么 之前 結點我們需要使用一個臨時變量保存。
為什么呢？ 如果當前指針遍歷到1結點，此時不保存上一個結點，我們就無法“回頭”找到 它了.之后結點可以通過 2->next 得到，只要保證 1->3 連接建立之前， 2的next值不被改就可以保證鏈表不會斷。因為2的next值提前被改了，那么我們就找不到3節(jié)點了。
基于以上結論，我們可以給原鏈表加一個頭結點，并且定義三個指針 f/s/t(first/second/third)，分別指向頭結點、 第 1 個結點、第 2 個結點。（在code 中使用了prevNode, swapLeft, swapRight 來表示）
結點 1 和 2交換完成之后， 指針后移2位（代碼層面就是保證不出現(xiàn)空指針異?；蛘叨五e誤） ，然后交換 3 和 4 結點。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode();
dummyNode.next = head;
// prevNode 遍歷鏈表時用
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;、
//標桿位后移2位
prevNode = prevNode.next.next;
}
return dummyNode.next;
}
}
時間復雜度： 整個鏈表需要遍歷一遍，所以算法時間復雜度的上限是 O(n)
空間復雜度： 不管鏈表有多長，運行算法需要額外開辟的空間總是常數(shù)級的，算法的空間復雜度是O(1)
方法二 遞歸
遞歸終止條件： 當前節(jié)點或下一節(jié)點為null
class Solution {
public ListNode swapPairs(ListNode head) {
////遞歸的終止條件
if(head == null || head.next == null) return head;
//假設鏈表是 1->2->3->4
//這句就先保存節(jié)點2
temp = head.next;
//繼續(xù)遞歸，處理節(jié)點3->4
//當遞歸結束返回后，就變成了4->3
//于是head節(jié)點就指向了4，變成1->4->3
head.next = swapPairs(temp.next);
//將2節(jié)點指向1, 2此時成為第一個節(jié)點
temp.next = head;
return temp;
}
}
時間復雜度： O(n)
空間復雜度： 遞歸棧O(n)
19. 刪除鏈表的倒數(shù)第N個節(jié)點
方法一 2 passes
第一遍循環(huán)找到鏈表長度len， 得到需要被移除節(jié)點位置
第二遍循環(huán)到節(jié)點 , 移除此節(jié)點
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)找到鏈表長度len， 得到需要被移除節(jié)點位置 length - n
while(curr != null){
curr = curr.next;
length++;
}
int delPosition = length - n;
//第二遍循環(huán)到delPosition節(jié)點, 移除此節(jié)點
curr = dummyHead;
while(delPosition > 0){
curr = curr.next;
delPosition--;
}
curr.next = curr.next.next;
return dummyHead.next;
}
}
時間復雜度： 遍歷兩遍 O(n)
空間復雜度： O(1)
方法二 快慢指針 1 pass
雙指針的經典應用，如果要刪除倒數(shù)第n個節(jié)點，讓fast移動n步，然后讓fast和slow同時移動，直到fast指向鏈表末尾。刪掉slow所指向的節(jié)點就可以了。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
//定義fast指針和slow指針，初始值為虛擬頭結點
ListNode fast = dummyHead;
ListNode slow = dummyHead;
//fast首先走n + 1步,
//只有這樣同時移動的時候slow才能指向刪除節(jié)點的上一個節(jié)點（方便做刪除操作）
for(int i = 0; i < n + 1; i++){
fast = fast.next;
}
//fast和slow同時移動，直到fast指向末尾
while(fast != null){
fast = fast.next;
slow = slow.next;
}
//刪除slow指向的下一個節(jié)點
slow.next = slow.next.next;
return dummyHead.next;
}
}
時間復雜度： 遍歷一遍 O(n)
空間復雜度： O(1)
面試題 02.07 鏈表相交 （同160）
給你兩個單鏈表的頭節(jié)點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表沒有交點，返回 null
方法一 HashSet
思路和算法
判斷兩個鏈表是否相交，可以使用哈希集合存儲鏈表節(jié)點。
首先遍歷鏈表 headA，并將鏈表 headA 中的每個節(jié)點加入哈希集合中。然后遍歷鏈表 headB，對于遍歷到的每個節(jié)點，判斷該節(jié)點是否在哈希集合中：
如果當前節(jié)點不在哈希集合中，則繼續(xù)遍歷下一個節(jié)點；
如果當前節(jié)點在哈希集合中，則后面的節(jié)點都在哈希集合中，即從當前節(jié)點開始的所有節(jié)點都在兩個鏈表的相交部分，因此在鏈表 headB 中遍歷到的第一個在哈希集合中的節(jié)點就是兩個鏈表相交的節(jié)點，返回該節(jié)點。
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;
}
//兩個鏈表不相交，返回 null
return null;
}
}
時間復雜度 O(m + n)
空間復雜度 O(m) m為鏈表A 長度
方法二 雙指針
用雙指針將時間復雜度降低為O(1)
思路：
走到盡頭見不到你，于是走過你來時的路，等到相遇時才發(fā)現(xiàn)，你也走過我來時的路。
如果兩個鏈表相交，則相交后的長度相同
設A的長度為a+c，B的長度為b+c；其中c為A、B的公共部分；
若相交，鏈表A： a+c, 鏈表B : b+c. a+c+b+c = b+c+a+c 。則會在c的起點相遇。若不相交，a +b = b+a 。因此相遇處是NULL
具體解釋：
假設headA, headB 長度分別為m,n。 非公共部分長度分別為a, b; 公共部分長度為c
情況一： 相交
如果a=b, 則指針pA,pB會同時達到c,pA = pB = c的開始節(jié)點， 返回相交節(jié)點；
如果a != b,則pA,pB會分別遍歷完headA, headB。 然后pA移到headB的頭節(jié)點，pB移到headA的頭節(jié)點， 兩指針繼續(xù)分別移動。在pA移動了a+c+b次，pB移動了b+c+a次后，到達公共部分c
情況二： 不相交
當m=n， pA,pB同時到達鏈表尾部，同時為null,返回null
當m != n, pA, pB 會各自遍歷完兩個headA, headB 兩個鏈表，pA移動m+n次，pB移動n+m次，同時變?yōu)閚ull, 返回null
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//設A的長度為a+c，B的長度為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的起始點處相遇
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;
}
}
時間復雜度 O(m + n)
空間復雜度 O(1)
雙指針相似思路：
并求出兩個鏈表長度的差值，然后讓curA移動到，和curB 末尾對齊的位置，
此時我們就可以比較curA和curB是否相同，如果不相同，同時向后移動curA和curB，如果遇到curA == curB，則找到交點.否則循環(huán)退出返回空指針。
142. 環(huán)形鏈表II
題意： 給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。
為了表示給定鏈表中的環(huán)，使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。
說明：不允許修改給定的鏈表。
方法一： 哈希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;
}
}
時間復雜度： O(n)
空間復雜度： O(n)
