leetcode - Reverse Linked List @ Sun, Mar 5, 2023 9:43 PM
leetcode - Reverse Linked List @ Mon, Mar 6, 2023 2:57 PM
Expand 33 lines ...
34
function reverseList(head: ListNode | null): ListNode | null {

34
function reverseList(head: ListNode | null): ListNode | null {

35
  // base case, breaking recursive loop

35
  // base case, breaking recursive loop

36
  if (head === null || head.next === null) return head;

36
  if (head === null || head.next === null) return head;

37
-
  // head.next.next.next 到 base case, 即最后一个节点(倒数第一个)
37
+
  // head.next.next.next 到 base case, 即最后一个节点(倒数第一个) 
38


38


39
  const newHead = reverseList(head.next);

39
  const newHead = reverseList(head.next);

40
+
  // last node 会进入 base case, 倒数第二个会进入下面的逻辑。

41
+
  // 处理完倒数第二个，函数栈推出进入倒数第三个。

42
+
  // -----------

40
  // 由于是递归，函数栈一直增加，FILO 其实是从后往前处理的。最后处理第一个节点。

43
  // 由于是递归，函数栈一直增加，FILO 其实是从后往前处理的。最后处理第一个节点。

41
-
  head.next.next = head;
44
+
  // 第一次进入该逻辑的 head 是 Formal parameters(形参)
42


45


46
+
  // head = penultimate node

47
+
  // last node -> next = head(penultimate node)

48
+
  // head = third last node

49
+
  // 此时 head.next 指向倒数第二个节点(last->[penultimate node])

50
+
  // [penultimate node]->next = head(third last node)

51
+
  // ... 

52
+
  head.next.next = head; // head.next.next 是上一个节点的引用。

53
+
  // 断掉倒数第二个 node 指向 last node 的指针。

54
+
  // ...

43
  head.next = null;

55
  head.next = null;

56
+
  // callstack pop，大部分情况下面的代码可以忽略。

44
  return newHead;

57
  return newHead;

45
};

58
};

46
```

59
```

47


60


48
## two pointers

61
## two pointers

Expand 31 lines ...