代碼隨想錄訓(xùn)練營第4天哑子，鏈表也要收尾啦饶套。
24. 兩兩交換鏈表中的節(jié)點(diǎn)
題目描述：
給你一個鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)芒填，并返回交換后鏈表的頭節(jié)點(diǎn)呜叫。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即空繁，只能進(jìn)行節(jié)點(diǎn)交換）。
解法一：設(shè)置虛擬頭節(jié)點(diǎn)
基本思路：建議畫圖
- 首先設(shè)置虛擬頭結(jié)點(diǎn) dummyHead朱庆，并將其指向原本的頭結(jié)點(diǎn)盛泡，且為當(dāng)前節(jié)點(diǎn) cur
進(jìn)入循環(huán)，終止條件為頭結(jié)點(diǎn)后面不存在兩個節(jié)點(diǎn) - 通過改變指針的方向來交換頭結(jié)點(diǎn)后面兩個點(diǎn)node1娱颊，node2的位置
- cur.next = node2
- node2.next = node1;
- node1.next = node2.next;
- 更新 cur 的位置傲诵，往后移一位
class Solution {
public ListNode swapPairs(ListNode head) {
//創(chuàng)建虛擬頭節(jié)點(diǎn)，將虛擬頭節(jié)點(diǎn)設(shè)成當(dāng)前節(jié)點(diǎn)cur
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode cur = dummyHead;
while(cur.next != null && cur.next.next != null){
ListNode node1 = cur.next;
ListNode node2 = cur.next.next;
//三部曲,注意順序
cur.next = node2;
node1.next = node2.next;
node2.next = node1;
cur = node1;
}
return dummyHead.next;
}
}
解法二：迭代法 （稍后更新）
19.刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)
題目描述：
給你一個鏈表维蒙，刪除鏈表的倒數(shù)第 n 個結(jié)點(diǎn)掰吕，并且返回鏈表的頭結(jié)點(diǎn)。
進(jìn)階：你能嘗試使用一趟掃描實(shí)現(xiàn)嗎颅痊？
解法一：快慢指針+虛擬頭節(jié)點(diǎn)
主旨：設(shè)置快慢指針，想讓快指針走n步局待，然后讓快慢指針同時走斑响，等快指針指向null的時候，刪除慢指針?biāo)傅狞c(diǎn)钳榨；
1.設(shè)置虛擬頭舰罚，初始化快慢指針，都指向虛擬頭
2.快指針走/n+1/步薛耻，為的是讓慢指針指向要刪的前一個節(jié)點(diǎn)营罢，方便鏈表操作
3.快慢指針同時走，快指針指向null時停
4.慢指針刪除它目前位置的下一個節(jié)點(diǎn)
5.返回頭節(jié)點(diǎn)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//初始設(shè)置饼齿，雙指針法
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode fast = dummyHead;
ListNode slow = dummyHead;
//先讓fast指針跑n個位置
for(int i=0; i<n;i++){
fast = fast.next;
}
//當(dāng)fast 在n 位上時饲漾，slow 和 fast 同時往前，直到fast走到底
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
}
面試題 02.07. 鏈表相交
給你兩個單鏈表的頭節(jié)點(diǎn) headA 和 headB 缕溉，請你找出并返回兩個單鏈表相交的起始節(jié)點(diǎn)考传。如果兩個鏈表沒有交點(diǎn)，返回 null证鸥。
解法一：常規(guī)解法
基本思路：
找出兩個鏈表交點(diǎn)的指針僚楞；比較指針，不是比較值
題目為了方便比較枉层，默認(rèn)數(shù)值相同則指針就相同泉褐！
1.設(shè)置currA，currB兩指針鸟蜡，分別指向兩個鏈表的表頭膜赃；
2.計算A，B長度矩欠；將長的鏈表設(shè)為A财剖，并且移動currA到B表頭的位置悠夯；讓currA和currB處于同一起跑線
3.currA，currB同時移動躺坟，如果指針相同沦补，則返回currA；沒有則返回null咪橙。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//初始化
ListNode currA = headA;
ListNode currB = headB;
int lenA = 0;
int lenB = 0;
//計算兩個鏈表的長度
while(currA != null){
lenA++;
currA = currA.next;
}
while(currB != null){
lenB++;
currB = currB.next;
}
//將當(dāng)前節(jié)點(diǎn)重新初始化頭節(jié)點(diǎn)
currA = headA;
currB = headB;
//確保A鏈表是長的那個
if(lenB > lenA){
int tempL = lenB;
lenB = lenA;
lenA = tempL;
ListNode tempN = currB;
currB = currA;
currA = tempN;
}
int gap = lenA - lenB;
//當(dāng)鏈表A被遍歷到和B鏈表一樣的位置時夕膀，currA 和 currB 齊頭并進(jìn)
for (int i = 0; i < gap;i++){
currA = currA.next;
}
while(currA != null){
if (currA == currB){
return currA;
}
currA = currA.next;
currB = currB.next;
}
return null;
}
}
解法二：高級解法
解題思路：把兩條鏈表相加，成為一條長的鏈表
headA先遍歷表A再去遍歷表B美侦；
headB先遍歷表B再去遍歷表A产舞；
當(dāng)A，B重合時：
·如果有公共節(jié)點(diǎn)菠剩，則停在公共節(jié)點(diǎn)上易猫；
·如果沒有公共節(jié)點(diǎn)，兩點(diǎn)只會都停在null上
因此具壮，返回A即可准颓；
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while(A != B){
A = A != null ? A.next : headB;
B = B != null ? B.next : headA;
}
return A;
}
}
142.環(huán)形鏈表II
給定一個鏈表的頭節(jié)點(diǎn) head ，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)棺妓。 如果鏈表無環(huán)攘已，則返回 null。
如果鏈表中有某個節(jié)點(diǎn)怜跑，可以通過連續(xù)跟蹤 next 指針再次到達(dá)样勃，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)性芬，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）峡眶。如果 pos 是 -1，則在該鏈表中沒有環(huán)批旺。注意：pos 不作為參數(shù)進(jìn)行傳遞幌陕，僅僅是為了標(biāo)識鏈表的實(shí)際情況。
不允許修改 鏈表汽煮。
解法一：快慢指針
基本思路：
- 設(shè)置 fast 和 slow 兩個指針搏熄，開始遍歷鏈表；初始化都在 head 節(jié)點(diǎn)暇赤。
- fast 每次走兩步心例，slow 每次走一步，如果存在環(huán)鞋囊，則 fast 和 slow 必定在環(huán)內(nèi)相遇止后；如果不存在環(huán)，則返回 null
- 當(dāng) fast 和 slow 相遇時，將 index1 設(shè)為 fast 的位置译株，將 index2 設(shè)為 head 的位置瓜喇；每次 index1 和 index2 都走一步，最終 index1 和 index2 會在環(huán)入口相遇歉糜。則返回 index1.
具體證明過程乘寒，見https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E6%80%9D%E8%B7%AF
public class Solution {
public ListNode detectCycle(ListNode head) {
// if (head == null || head.next == null){
// return null;
// }
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if (fast == slow){
ListNode index1 = fast;
ListNode index2 = head;
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
