24.兩兩交換鏈表中的節(jié)點
題目描述：
給你一個鏈表搀突，兩兩交換其中相鄰的節(jié)點仰迁，并返回交換后鏈表的頭節(jié)點徐许。你必須在不修改節(jié)點內部的值的情況下完成本題（即筒扒，只能進行節(jié)點交換）
示例 1：
輸入：head = [1,2,3,4]
輸出：[2,1,4,3]
示例 2：
輸入：head = []
輸出：[]
示例 3：
輸入：head = [1]
輸出：[1]
解題思路
舉例：[1,2,3,4] 利用虛擬頭節(jié)點 -> [0,1,2,3,4]
var swapPairs = function(head) {
let dymmic = new ListNode(0, head);
let cur = dymmic;
while(cur && cur.next && cur.next.next) {
let pre = cur.next; // pre = [1,2,3,4]
cur.next = cur.next.next; // cur = [0,2,3,4]
let next = cur.next.next; // next = [3,4]
cur.next.next = pre; // cur = [0,2,1,2,3,4]
pre.next = next; // pre = [1,3,4]
cur = pre; // cur = [0,2,1,3,4]
}
return dymmic.next;
};
- 時間復雜度：O(n)
- 空間復雜度：O(1)
19.刪除鏈表的倒數(shù)第 N 個結點
題目描述：
給你一個鏈表绊寻，刪除鏈表的倒數(shù)第 n 個結點悬秉，并且返回鏈表的頭結點澄步。
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]
示例 2：
輸入：head = [1], n = 1
輸出：[]
示例 3：
輸入：head = [1,2], n = 1
輸出：[1]
解題思路
- 利用快慢指針
- 快指針：先一步移動n個步數(shù)
- 慢指針：等快指針到達n個步數(shù)后和泌，快慢指針一同移動村缸，直到快指針的next為null，此時慢指針的指向即為倒數(shù)第N的節(jié)點
var removeNthFromEnd = function(head, n) {
let dymmic = new ListNode(0, head);
let fast = dymmic;
let slow = dymmic;
while(n--) {
fast = fast.next
}
while(fast.next) {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return dymmic.next;
};
- 時間復雜度：O(n)
- 空間復雜度：O(1)
面試題 02.07. 鏈表相交
題目描述：
給你兩個單鏈表的頭節(jié)點 headA 和 headB 武氓，請你找出并返回兩個單鏈表相交的起始節(jié)點梯皿。如果兩個鏈表沒有交點县恕，返回 null 忠烛。
圖示兩個鏈表在節(jié)點c1開始相交：
image.png
題目數(shù)據(jù) 保證 整個鏈式結構中不存在環(huán)。
注意师坎，函數(shù)返回結果后，鏈表必須 保持其原始結構 。
示例1：
image.png
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點的值為 8 （注意遏乔，如果兩個鏈表相交則不能為 0）寿弱。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]按灶，鏈表 B 為 [5,0,1,8,4,5]症革。
在 A 中，相交節(jié)點前有 2 個節(jié)點鸯旁；在 B 中噪矛，相交節(jié)點前有 3 個節(jié)點量蕊。
示例 2：
image.png
輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節(jié)點的值為 2 （注意，如果兩個鏈表相交則不能為 0）艇挨。
從各自的表頭開始算起残炮，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]缩滨。
在 A 中势就，相交節(jié)點前有 3 個節(jié)點；在 B 中脉漏，相交節(jié)點前有 1 個節(jié)點苞冯。
示例 3：
image.png
輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]侧巨，鏈表 B 為 [1,5]舅锄。
由于這兩個鏈表不相交，所以 intersectVal 必須為 0司忱，而 skipA 和 skipB 可以是任意值皇忿。
這兩個鏈表不相交，因此返回 null 坦仍。
解題思路
- 首先計算 A,B 兩個鏈表分別的長度
- 計算差值diffDep鳍烁，讓長鏈表首先移動diffDep個步數(shù)
- 再讓A，B兩個鏈表同時移動繁扎，直到找到相同的頭節(jié)點老翘，返回即可
- 否則返回null
注意
1 判斷頭節(jié)點是否相等：比較的是節(jié)點指向而不是節(jié)點值
var getIntersectionNode = function(headA, headB) {
let A = headA;
let Alen = 0
let B = headB;
let Blen = 0;
while(A) {
A = A.next;
Alen++
}
while(B) {
B = B.next;
Blen++
}
let diffDep = Math.abs(Alen - Blen)
while (diffDep--) {
if (Alen > Blen) {
headA = headA.next
} else {
headB = headB.next
}
}
while(headA) {
if (headA === headB) {
return headA
} else {
headA = headA.next
headB = headB.next
}
}
return null
};
- 時間復雜度：O(n+m)
- 空間復雜度：O(1)
142. 環(huán)形鏈表 II
題目描述：
給定一個鏈表的頭節(jié)點 head ，返回鏈表開始入環(huán)的第一個節(jié)點锻离。 如果鏈表無環(huán)铺峭，則返回 null。
如果鏈表中有某個節(jié)點汽纠，可以通過連續(xù)跟蹤 next 指針再次到達卫键，則鏈表中存在環(huán)。
為了表示給定鏈表中的環(huán)虱朵，評測系統(tǒng)內部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）莉炉。
如果 pos 是 -1，則在該鏈表中沒有環(huán)碴犬。注意：pos 不作為參數(shù)進行傳遞絮宁，僅僅是為了標識鏈表的實際情況。
不允許修改鏈表服协。
示例 1：
image.png
輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)绍昂，其尾部連接到第二個節(jié)點。
示例 2：
image.png
輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點窘游。
示例 3：
image.png
輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)唠椭。
解題思路
- 判斷鏈表是否為環(huán)行鏈表
- 如果為環(huán)形鏈表，如何找到環(huán)形入口
如何判斷鏈表是否為環(huán)形
使用快慢指針法忍饰，分別設置fast和slow贪嫂，從頭節(jié)點出發(fā)，fast一次移動2個節(jié)點艾蓝，slow一次移動1個節(jié)點力崇，如果途中相遇，則為環(huán)形鏈表赢织。
如何找到環(huán)形入口
從頭節(jié)點出發(fā)1個指針亮靴，從相遇節(jié)點出發(fā)1個指針，這兩個指針每次同時只移動1個節(jié)點敌厘，當這兩個指針相遇的時候就是環(huán)形入口的節(jié)點。
var detectCycle = function(head) {
if (!head || !head.next) {
return null
}
let fast = head.next.next;
let slow = head.next;
while(fast && fast.next && fast !== slow) {
slow = slow.next
fast = fast.next.next
}
if (!fast || !fast.next) {
return null
}
slow = head;
while (slow !== fast) {
slow = slow.next
fast = fast.next
}
return slow;
};
環(huán)形鏈表推理請參考：代碼隨想錄
另外友友們朽合，有沒有好用的畫圖軟件推薦呀
