LeetCode题解： 206. 反转链表，JavaScript，递归，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/reverse-linked-list/

假设有链表1->2->3->4->5->NULL，那么递归的步骤如下：

1. 当递归到最深处时，此时运行的是reverseList(5)，那么返回的是5。
2. reverseList(5)的上一层就是reverseList(4)，此时运行步骤如下：
   • headNext其实是5，此时链表还是`1->2->3->4->5->NULL``
   • 当运行head.next.next = head;后，实际上是把5的指向修改成了4，此时链表变成了1->2->3->4<=>5，4和5互相指向了。
   • 当运行head.next = null;后，链表变成了1->2->3->4<-5+4->NULL，需要注意的是，此时4被3和5同时指向，而且4还有个隐藏的指向为null。
   • 上面的写法只是为了帮助理解，实际上链表已经被拆成了两段，分别为1->2->3->4和NULL<-4<-5。
   • 最后reverseList(4)的返回值其实是5->4
3. reverseList(4)的上一层是reverseList(3)，此时运行步骤如下：
   • headNext其实是5->4，此时链表是1->2->3->4<-5+4->NULL
   • 当运行head.next.next = head;后，3和4的指向被翻转，而此时还存在一个5->4的指向，那么链表变成了1->2->3<=>4<->5，3和4互相指向了。
   • 当运行head.next = null;后，链表变成了1->2->3<-4<-5+3->NULL，需要注意的是，此时3被2和4同时指向，而且3还有个隐藏的指向为null。
   • 上面的写法只是为了帮助理解，实际上链表已经被拆成了两段，分别为1->2->3和NULL<-3<-4<-5。
   • 最后reverseList(3)的返回值其实是5->4->3。
4. 之后的递归就是不断重复上面的步骤，最终返回的结果就为NULL<-1<-2<-3<-4<-5。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  // 避免节点为空，或者只有1个节点的情况
  if (head === null || head.next === null) {
    return head;
  }

  // 请注意下面注释中的head、head.prev、head.next都指的是原数组中的节点

  // reverseList返回的节点实际上就是原链表的最后一个节点，新链表的第一个节点。
  const headNext = reverseList(head.next);
  // 将head.next指向head，完成两者指向的翻转
  // 但此时的指向实际变成了head.prev -> head <=> head.next
  // 也就是说head和head.next互相指向了
  head.next.next = head;
  // 清空head的指向
  head.next = null;

  // 将head.next返回给上层调用
  return headNext;
};