leetcode - Reverse Linked List
Published by powerfulyang on Feb 18, 2023
反转链表,这次你一定要懂
Reverse Linked List,这个不会建议回炉重造了(说的就是我)。
recursive
- Base Case: Rather than a condition to keep running, recursive algorithms reach a point to stop and return. This point is commonly referred to as the base case.
- Each time you call the function, an argument must change. One argument in particular should be changing towards the base case.
- Establish your base case. Figure out when the recursion ends! Without a place to stop you’ll wind up overflowing the call stack.
1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13function reverseList(head: ListNode | null): ListNode | null {
14 // base case, breaking recursive loop
15 if (head === null || head.next === null) return head;
16 // head.next.next.next 到 base case, 即最后一个节点(倒数第一个)
17 const newHead = reverseList(head.next);
18 // last node 会进入 base case, 倒数第二个会进入下面的逻辑。
19 // 处理完倒数第二个,函数栈推出进入倒数第三个。
20 // -----------
21 // 由于是递归,函数栈一直增加,FILO 其实是从后往前处理的。最后处理第一个节点。
22 // 第一次进入该逻辑的 head 是 Formal parameters(形参)
23 // head = penultimate node
24 // last node -> next = head(penultimate node)
25 // head = third last node
26 // 此时 head.next 指向倒数第二个节点(last->[penultimate node])
27 // [penultimate node]->next = head(third last node)
28 // ...
29 head.next.next = head; // head.next.next 是上一个节点的引用。
30 // 断掉倒数第二个 node 指向 last node 的指针。
31 // ...
32 head.next = null;
33 // callstack pop,大部分情况下面的代码可以忽略。
34 return newHead;
35};
two pointers
1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13function reverseList(head: ListNode | null): ListNode | null {
14 let prev = null;
15 let cur = head;
16 // 从头开始处理
17 while (cur !== null) {
18 // store next pointer
19 const next = cur.next;
20 // break next pointer and link handled nodes
21 cur.next = prev;
22 // store handled nodes
23 prev = cur;
24 // next loop
25 cur = next;
26 }
27 return prev;
28};