Chipmunk & Panda

-- 鼠熊部落格

All work and no play makes Jack a dull boy.

反转链表

  数据结构与算法    

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof

初见（迭代法）

首先要把头节点的前一个结点存储下来，然后就是对每个节点执行：

  1. 存储下一个节点
  2. 更新当前节点的 next 为前一个结点
  3. 存储当前节点，用于下一个节点更新 next
  4. 切换到下一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
function ListNode(val) {
    this.val = val;
    this.next = null;
}
*/

var reverseList = function (head) {
  if (!head || !head.next) {
    return head
  }

  let node = head
  let nodeBefore = null // 实际是存储了 head 的前一个节点
  let nodeAfter = null

  while (node) {
    nodeAfter = node.next
    node.next = nodeBefore
    nodeBefore = node
    node = nodeAfter
  }

  return nodeBefore
}