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.
typescript
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

typescript
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};