雙指標解“鏈表”題也太香了叭！
同步雙指標
1 查找鏈表中倒數第 k 個節點
劍指Offer22.鏈表中倒數第k個節點
思路：
-
假設鏈表的長度為
n，不難得出倒數第k個節點即為整數第n + 1 - k， -
如果一個指標從頭節點開始走
k步（頭節點算作第1步），則還需n + 1 - k步才能走完鏈表（到達尾節點的next，即 null）， -
我們用雙指標，一個指標先走
k步，然后兩個指標同時走n + 1 - k步，其中一個指標走完鏈表，另一個指標走到第n + 1 - k個節點處，即倒數第k個節點
代碼
JS
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function (head, k) {
let p1 = head;
// 注意此處 i < k - 1，因為 p1 賦值時算作第 1 步
for (let i = 0; i < k - 1; i++) {
p1 = p1.next;
}
let p2 = head;
p1 = p1.next; // 同理 p2 賦值算作第 1 步，所以 p1 也要走 1 步
while (p1) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
};
// 時間復雜度 O(n) n為鏈表長度
// 空間復雜度 O(1)
TS
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function getKthFromEnd(head: ListNode | null, k: number): ListNode | null {
const dummyHead = new ListNode();
dummyHead.next = head;
let p1 = dummyHead;
for (let i = 0; i < k; i++) {
p1 = p1.next;
}
let p2 = dummyHead;
while (p1) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
// 時間復雜度 O(n) n為鏈表長度
// 空間復雜度 O(1)
注：JS 和 TS 的實作略微有些不同，TS 中添加了一個虛擬頭節點，虛擬頭節點在解決鏈表相關的一些題目時非常有用，體會一下不用虛擬頭節點和使用虛擬頭節點的差別
2 洗掉鏈表中倒數第 k 個節點
19.洗掉鏈表的倒數第N個結點
思路
-
洗掉和查找倒數第 k 個節點的思路大致相同
-
唯一的區別是洗掉倒數第 k 個節點時我們應該查找倒數第 k + 1 個節點，然后讓其 next 指向 next 的 next，
因為我們要查找倒數第 k + 1 個節點，所以應該讓第一個指標先走 k + 1 步
-
此外洗掉的有可能是第 1 個節點，見示例2，此時洗掉的是倒數第 1 個節點，所以我們要查找倒數第 2 個節點，然而鏈表總共才 1 個節點，因此我們引入虛擬頭節點來解決
代碼
JS
var removeNthFromEnd = function (head, n) {
const dummyHead = new ListNode();
dummyHead.next = head; // 將虛擬頭節點接入鏈表
let p1 = dummyHead;
// p1 先走 n + 1 步
for (let i = 0; i < n + 1; i++) {
p1 = p1.next;
}
let p2 = dummyHead;
while (p1) {
p1 = p1.next;
p2 = p2.next;
}
p2.next = p2.next.next;
// 注意不是回傳 head，因為 head 有可能被洗掉
return dummyHead.next;
};
// 時間復雜度 O(n) n為鏈表長度
// 空間復雜度 O(1)
TS
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummyHead = new ListNode();
dummyHead.next = head;
let p1 = dummyHead;
for (let i = 0; i < n + 1; i++) {
p1 = p1.next;
}
let p2 = dummyHead;
while (p1) {
p1 = p1.next;
p2 = p2.next;
}
p2.next = p2.next.next;
return dummyHead.next;
}
注：嘗試不用虛擬頭節點解此題，體會虛擬頭節點的妙處
3 查找兩條鏈表的相交節點
160. 相交鏈表
思路
- 雙指標 p1 和 p2 分別從 headA 和 headB 出發
- 如果 p1 走完了鏈表 A，就從 headB 接著走；同理，如果 p2 走完了鏈表 B，就從 headA 接著走
- 在這種走法下，p1 和 p2 一定同時走完
- 如果兩條鏈表相交，那么 p1 和 p2 一定會在交點相遇，因為從交點開始到結束點，兩條鏈表的路徑是相同的，于是 p1 和 p2 從結束點向前推能同時到達交點
- 如果兩條鏈表不相交，則 p1 和 p2 全程不會相遇
代碼
JS
var getIntersectionNode = function (headA, headB) {
let p1 = headA;
let p2 = headB;
while (p1 || p2) {
if (p1 === p2) return p1;
p1 = p1 ? p1.next : headB;
p2 = p2 ? p2.next : headA;
}
return null;
};
// 時間復雜度 O(n + m) m、n 分別為兩條鏈表長度
// 空間復雜度 O(1)
TS
function getIntersectionNode(
headA: ListNode | null,
headB: ListNode | null
): ListNode | null {
let p1 = headA;
let p2 = headB;
while (p1 || p2) {
if (p1 === p2) return p1;
p1 = p1 ? p1.next : headB;
p2 = p2 ? p2.next : headA;
}
return null;
}
快慢雙指標
1 查找鏈表的中間節點
876. 鏈表的中間結點
思路
- 這題我們讓兩個指標同時走，不過兩個指標的速度不同，分為快慢指標
- 我們讓慢指標每次走 1 步，快指標每次走 2 步
- 當快指標走完鏈表，即指向 null，慢指標就走到了中間節點的位置
代碼
JS
var middleNode = function (head) {
const dummyHead = new ListNode();
dummyHead.next = head;
let fastP = dummyHead;
let slowP = dummyHead;
while (fastP) {
slowP = slowP.next;
fastP = fastP.next;
fastP && (fastP = fastP.next);
}
return slowP;
};
// 時間復雜度 O(n) n 為鏈表長度
// 空間復雜度 O(1)
TS
function middleNode(head: ListNode | null): ListNode | null {
const dummyHead = new ListNode();
dummyHead.next = head;
let fastP = dummyHead;
let slowP = dummyHead;
while (fastP) {
slowP = slowP.next;
fastP = fastP.next;
fastP && (fastP = fastP.next);
}
return slowP;
}
2 判斷鏈表中是否有環
141. 環形鏈表
思路
- 設定快慢兩指標 fastP 、slowP
- fastP 每次走 2 步，slowP 每次走 1 步
- 如果鏈表中沒有環，那么 fastP 最侄訓先走到 null
- 如果鏈表中有環，那么 fastP 會先進入環，并在環中轉圈
- 當 slowP 進入環后，fastP 開始追趕 slowP，最終一定能追上
- 當 fastP 追上 slowP 時，若 slowP 走了 n 步，不難得出，fastP 走了 2n 步或 2n - 1 步
代碼
JS
var hasCycle = function (head) {
// 如果鏈表為慷訓只有 1 個節點，一定無環
if (!head || !head.next) return false;
let slowP = head;
let fastP = head.next; // slowP 賦值為 head 相當于走了 1 步，故 fastP 要走 2 步
while (fastP) {
slowP = slowP.next;
fastP = fastP.next;
if (slowP === fastP) return true;
fastP && (fastP = fastP.next);
}
return false;
};
// 時間復雜度 O(n) n 為鏈表長度
// 空間復雜度 O(1)
TS
function hasCycle(head: ListNode | null): boolean {
if (!head || !head.next) return false;
let slowP = head;
let fastP = head.next;
while (fastP) {
slowP = slowP.next;
fastP = fastP.next;
if (slowP === fastP) return true;
fastP && (fastP = fastP.next);
}
return false;
}
3 查找鏈表中環的入口節點
142. 環形鏈表 II
思路
- 此題和上一題的思路大致相同，不過在上一題的基礎上更進一步
- 上一題中提到，如果快指標追上慢指標，且假設 slowP 走了 n 步，不難得出，fastP 走了 2n 步或 2n - 1 步，出現走 2n - 1 步的原因是可能存在 fastP 最后只走 1 步就追上 slowP 的情況
- 不過即使規定 fastP 一定要走偶數步，fastP 和 slowP 也一定能在某點相遇，因為在 fastP 走 2 步，slowP 走 1 步的前提下，兩者的間距會 -1，所以最終兩者會相遇
- 現在設 slowP 走了 n 步，fastP 走了 2n 步，兩者相遇
- 則 fastP 比 slowP 多走了 n 步，這 n 步是環周長的整數倍
- 假設 slowP 從環起點開始走了 k 步后，兩者相遇，則從鏈表頭節點開始走 n - k 步（頭節點算第 1 步）就能到達環起點
- 而從環起點走 k 步到達相遇點，再走 n - k 步就能到達相遇點，因為從環起點走 k + n - k = n 步回到環起點（見第5點，因為 n 是環周長的整數倍）
- 所以我們可以先用快慢指標找到兩者的相遇點，然后讓快指標從頭開始，慢指標從相遇點開始，并且兩者變成同步指標，則兩者再次相遇即為環的起點
代碼
JS
var detectCycle = function (head) {
if (!head || !head.next) return null;
let fastP = head.next;
let slowP = head;
while (fastP) {
if (fastP === slowP) break;
slowP = slowP.next;
fastP = fastP.next;
fastP && (fastP = fastP.next);
}
if (!fastP) return null;
fastP = head;
slowP = slowP.next; // 注意 fastP 賦值為頭節點相當于已經走了 1 步，所以 slowP 也要走 1 步
while (fastP !== slowP) {
fastP = fastP.next;
slowP = slowP.next;
}
return fastP;
};
// 時間復雜度 O(n)
// 空間復雜度 O(1)
TS
function detectCycle(head: ListNode | null): ListNode | null {
// 這里我們把頭節點當作虛擬節點
let fastP = head;
let slowP = head;
while (fastP) {
slowP = slowP.next;
fastP = fastP.next;
fastP && (fastP = fastP.next);
if (fastP === slowP) break;
}
if (!fastP) return null;
fastP = head;
slowP = slowP;
while (fastP !== slowP) {
fastP = fastP.next;
slowP = slowP.next;
}
return fastP;
}
注：我們在 TS 中把頭節點當做了虛擬節點，體會兩種解法的細微差別
總結
事實上，使用雙指標的鏈表題還有很多，這里就舉幾個常見的栗子??，并且在鏈表題中虛擬頭節點也是個很棒的技巧，有時可以減少很多額外的判斷
完結撒花??
公眾號【今天也要寫bug】
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/503293.html
標籤：JavaScript
上一篇：吃貨聯盟訂餐系統