Reverse Linked List
•--
Reverse a singly linked list using iterative approach with pointer manipulation
Reverse a singly linked list and return the new head
問題描述
給你單鏈表的頭節點 head，請你反轉鏈表，並返回反轉後鏈表的頭節點。
範例
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
輸入：head = [1,2]
輸出：[2,1]
輸入：head = []
輸出：[]
限制條件
- 鏈表中節點的數目範圍是
[0, 5000] -5000 <= Node.val <= 5000
解題思路
### 三指針技巧 使用 prev、curr、next 三個指針來操作鏈表
### 逐步反轉 遍歷鏈表，逐個反轉每個節點的指向
### 更新指針 每次反轉後更新三個指針的位置
解決方案
typescript
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 reverseList(head: ListNode | null): ListNode | null {
type Pointers = Record<'prev' | 'curr', ListNode | null>;
const pointers: Pointers = {
prev: null,
curr: head,
};
while (pointers.curr) {
const updatePointers = ({ curr, prev }: Pointers) => ({
next: prev,
newPrev: curr!,
newCurr: curr!.next,
});
const { next, newPrev, newCurr } = updatePointers(pointers);
pointers.curr.next = next;
pointers.prev = newPrev;
pointers.curr = newCurr;
}
return pointers.prev;
}