题目内容

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

之前有过一题反转数组，反转链表思想上应该上差不多，但是JavaScript基本都是数组一把梭，没有像别的语言，有那么多的数据类型。所以JSer可能在链表思想上会稍显吃亏。

这题也是一样，明面上看着很简单。但是具体写代码可能还真会不知如何下手。

题目的默认模板中给出了对单链表的具体定义，即有值有next指针。

function ListNode(val, next) { 
  this.val = (val===undefined ? 0 : val)
  this.next = (next===undefined ? null : next)
}

解法一，新开栈覆盖原链表

var reverseList = function (head) {
  // 头节点不存在直接返回
  if (head === null || head.next === null) return head

  // 新开一个栈覆盖原链表的写法
  let stack = []
  // 这里是head.next而不是head，head没了是head.next都没了的下一步，head.next为null即意味着已经走到了单链表的尽头
  while (head.next !== null) {  
    stack.push(head)            // 存储拿到的每一个节点  
    head = head.next
  }
  // 执行完后数组里就是[1,2,3,4]，因为5的next的是null

  let realHead = head;          // 保存一份当时的尾节点，到最后反转完就是头节点
  // 把刚刚入的栈全部出完
  while (stack.length !== 0) {
    head.next = stack.pop();    // 上面遍历完一遍之后，head已经在5的位置了，此时就很方便的往回指，5.next = 4
    head = head.next;           // 赋值完后，head朝前走，head = 4
  }

  head.next = null;             // 将末尾的next置空
  return realHead;              // 5所在的节点
};

解法二，新开栈新链表

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

  let stack = [];               // 新开一个栈
  let node = head;              // 保存一份当前的头节点
  while (node) {
    stack.push(node.val);       // 往栈里存节点的数据
    node = node.next;
  }
  // 执行完上述while，栈里刚好是12345

  // 构造新的头节点，头节点的值，即是刚刚链表的末尾现在的栈顶5
  const newHead = {
    val: stack.pop(),
    next: null
  };
  node = newHead;
  // 直到栈里的数据都出完
  while (stack.length) {
    // 将当前的节点指向新产生的节点，
    node.next = {
      val: stack.pop(),
      next: null
    };
    // 更新当前的节点
    node = node.next;
  }
  return newHead;
}

解法三，三指针法

var reverseList = function (head) {
  if (head == null) return null

  let prev = null
  let cur = head
  let next = head
  while (cur) {
    // 传统写法
    next = cur.next       // next提前去占位，防止下一步执行之后，失去原有的cur指向
    cur.next = prev       // 断掉已有的链接，指针反指向前
    prev = cur            // 更新prev的位置，向前加1，这一步必须在下一步之前，否则更新cur指向之后，cur的引用就完全断了
    cur = next            // 更新cur的位置，向前加1，这也是链表前进的原因

    // es6解构赋值的写法
    // 使用解构赋值就不必产生一个中间变量next，而可以通过直接将cur.next赋值给cur，使得链表前进
    // [cur.next, prev, cur] = [prev, cur, cur.next]
  }
  return prev
}