LeetCode

206. 反转链表

迭代（双指针）

pre 和 cur 两个指针，怎么理解？ pre 和 cur 是两个普通的JS变量，但是变量的值存的是对象的地址（链表节点）。

var reverseList = function(head) {
  // 1. 初始化，cur指向head， pre指向null
    let cur = head
    let pre = null 
  // 2. 确认循环终止条件
    while(cur !== null){
      // a. 临时变量存 cur.next 
        let tmp = cur.next
      // b. 反转链表节点
        cur.next = pre
      // c. 两个指针向右移动，注意先pre = cur !
        pre = cur 
        cur = tmp 
    }
    return pre
};

递归写法

// 1. 初始化，head 给 cur， null给 pre
var reverse = function (pre, cur) {
  // 2. 终止条件
  if (cur === null) return pre
  let tmp = cur.next // A.
  cur.next = pre     // B.   一定是先A后B 
  // 函数的参数传递，是从左到右的，pre = cur, cur = tmp
  return reverse(cur, tmp)
}
var reverseList = function (head) {
  return reverse(null, head)
}

为什么下面这种也可以？

// 定义 reverse 函数

var reverse = function (cur, pre) {
  if (cur === null) return pre
  let tmp = cur.next
  cur.next = pre 
  // 传递到后一个时，cur = tmp 引用值， pre = cur 引用值
  // 函数参数传递是值传递，所以这里顺序不影响了？！
  return reverse(tmp, cur)
  // 如果参数是引用类型，那么这个副本实际上是原引用的一个复制，
  // 也就是说函数接收的其实是引用的地址
}

// 定义 reverseList 函数
var reverseList = function (head) {
  return reverse(head, null)
}

PS JS中的链表

// 链表节点的类
function ListNode(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
}
// ListNode 就是一个最简单的链表节点，val 是节点的值，
// next 是一个指向下一个节点的引用。

创建一个包含已知值的链表

let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;

console.log(node1.val); // 输出：1
console.log(node1.next.val); // 输出：2
console.log(node1.next.next.val); // 输出：3

在链表中，让 pre 和 cur 指针指向不同的节点非常简单，只需要将它们赋值为对应节点即可。 如果要让 pre 指向 node1，cur 指向 node2，可以这么写：

let pre = node1;
let cur = node2;

注意 pre 和 cur 现在实际上并没有创建任何新的节点，它们只是创建了一个新的引用，指向了已经存在的节点。

参考

• 帮你拿下反转链表 | LeetCode：206.反转链表 | 双指针法 | 递归法_哔哩哔哩_bilibili