Middle of the Linked List
•--
Find the middle node of a linked list using two-pointer technique
Find the middle node of a linked list using fast and slow pointers
問題描述
給你單鏈表的頭節點 head，請你返回鏈表的中間節點。
如果有兩個中間節點，則返回第二個中間節點。
範例
輸入：head = [1,2,3,4,5]
輸出：[3,4,5]
解釋：鏈表只有一個中間節點，值為 3
輸入：head = [1,2,3,4,5,6]
輸出：[4,5,6]
解釋：鏈表有兩個中間節點，值分別為 3 和 4，返回第二個節點
限制條件
- 鏈表的節點數範圍是
[1, 100] 1 <= Node.val <= 100
解題思路
### 雙指針設置 設置快指針和慢指針，都從頭節點開始
### 移動規則 快指針每次移動兩步，慢指針每次移動一步
### 終止條件 當快指針到達鏈表末尾時，慢指針正好在中間位置
解決方案
typescript
/**
* Definition for singly-linked list.
*/
export 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;
}
}
export function middleNode(head: ListNode | null): ListNode | null {
// Handle empty linked list
if (!head)
return null;
let slowPointer = head;
let fastPointer = head;
// Continue moving while:
// 1. fastPointer is not null (handles odd length)
// 2. fastPointer.next is not null (handles even length)
while (fastPointer && fastPointer.next) {
// Because of while condition, slowPointer definitely exists
slowPointer = slowPointer.next as ListNode;
// Move fast pointer two steps
fastPointer = fastPointer.next.next as ListNode;
}
return slowPointer;
}