参考文章：

  1. 腾讯面试官：删除链表的节点，怎么删？；
  2. 反转链表！；
  3. 反转链表 II ！；

前言

单向链表的结构如：A({ val: 1, next: B }) -> B({ val: 2, next: C }) -> … -> N({ val: n, next: null })

首先提供快速生成链表的代码：

  1. function createList(len) {
  2.   var count = 0;
  3.   var head = { val: count };
  4.   var node =  head;
  6.   while (count < len) {
  7.     count++;
  8.     node.next = { val: count };
  9.     node = node.next;
  10.   }
  12.   // 鉴于JavaScript变量类型的特殊性，最后一个节点的next设置为"none"便于判断
  13.   if (!node.next) {
  14.     node.next = 'none';
  15.   }
  17.   return head;
  18. }

测试验证：

  1. console.log(createList(3));
  3. // 打印结果: 
  4. // {"val":0,"next":{"val":1,"next":{"val":2,"next":{"val":3,"next":"none"}}}}

删除单向链表节点

代码如下：

  1. function deleteNode(head, val) {
  2.   // 特殊情况处理，删除的节点是头结点时，比较特别
  3.   if (head.val == val) return head.next;
  5.   // 设置两个指针，一个指针指向当前的节点
  6.   var pre = head;
  8.   // 一个指针指向当前节点的下一节点
  9.   var cur = head.next;
  11.   // 当 cur 为空 或 cur 节点值等于 val 时跳出跳出循环
  12.   while (cur === 'none' && cur.val != val) {
  14.       // 两个指针不断的向前移动
  15.       // pre 来到 cur 的位置
  16.       pre = cur;
  18.       // cur 来到下一个节点位置
  19.       cur = cur.next;
  20.   }
  22.   // 相当于覆盖掉了 cur 的节点值
  23.   pre.next = cur.next;
  25.   // 最后返回链表头结点就行
  26.   return head;
  27. }

测试验证：

  1. var head = createList(4);
  2. console.log('before', JSON.stringify(head));
  3. head = deleteNode(head, 1);
  4. console.log('after', JSON.stringify(head));
  6. // 打印结果:
  7. // before {"val":0,"next":{"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":"none"}}}}}
  8. // after {"val":0,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":"none"}}}}

全局反转链表

代码如下：

  1. function reverseList(head) {
  2.   // 寻找递归终止条件
  3.   // 1、head 指向的结点为 none 
  4.   // 2、head 指向的结点的下一个结点为 none 
  5.   // 在这两种情况下，反转之后的结果还是它自己本身
  6.   if( head == 'none' || head.next == 'none')  return head;
  8.   // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
  9.   // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
  10.   var cur = reverseList(head.next);
  12.   // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
  13.   // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
  14.   // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
  15.   // 等号右侧为 head，意思就是设置 5 的下一个节点是 4
  17.   // 这里出现了两个 next
  18.   // 第一个 next 是「获取」 head 的下一节点
  19.   // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
  20.   head.next.next = head;
  22.   // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
  23.   // 否则会发生无限循环
  24.   head.next = 'none';
  26.   // 我们把每次反转后的结果传递给上一层
  27.   return cur;
  28. }

测试验证：

  1. var head = createList(4);
  2. console.log('before', JSON.stringify(head));
  3. head = reverseList(head);
  4. console.log('after', JSON.stringify(head));
  6. // 打印结果:
  7. // before {"val":0,"next":{"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":"none"}}}}}
  8. // after {"val":4,"next":{"val":3,"next":{"val":2,"next":{"val":1,"next":{"val":0,"next":"none"}}}}}

局部反转链表

代码如下：

  1. function reverseBetween(head, left, right) {
  2.   // 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
  3.   // 设置虚拟节点的目的是为了让原链表中所有节点就都可以按照统一的方式进行翻转
  4.   // 比如如果翻转的区间包含了原链表中的第一个位置，那么如果不设置dummy
  5.   // 在翻转的过程中需要设置其它的临时变量来保持第一位置节点的指针
  6.   var dummy = { val: -1 };
  8.   // 让虚拟节点指向原链表的头部
  9.   dummy.next = head;
  11.   // 设置一个指针，指向以虚拟头节点为链表的头部位置
  12.   var pre = dummy;
  14.   // 设置一个指针，指向原链表的头部位置
  15.   var cur = head;
  17.   // 从虚拟头节点出发，pre 走 left 步找到需要翻转的左区间
  18.   // for 循环结束后，pre 的右节点是需要翻转的节点
  19.   // for 循环结束后，cur 指向的就是需要翻转的节点
  20.   for (var i = 0; i < left; i++) {
  21.     // pre 不断的向右移动，直到走到翻转的左区间为止
  22.     pre = pre.next;
  23.     // cur 不断的向右移动，找到了需要翻转的第一个节点
  24.     cur = cur.next;
  25.   }
  27.   // 开始翻转这些节点
  28.   // 初始: 0 --> 1 --> 2 --> 3 --> 4，cur.next = 2
  29.   // 第一次循环，结果: 0 --> 2 --> 1 --> 3 --> 4，cur.next = 3
  30.   // 第二次循环，结果: 0 --> 2 --> 3 --> 1 --> 4，cur.next = 4
  31.   for (var i = 0; i < right - left; i++) {
  32.     // 设置临时变量，保存当前需要翻转节点的后面的节点
  33.     var temp = cur.next;
  35.     cur.next = cur.next.next;
  36.     temp.next = pre.next;
  37.     pre.next = temp;
  38.   }
  40.   // 最后返回虚拟头节点的下一个节点，因为虚拟节点不在链表中
  41.   return dummy.next;
  42. }

测试验证：

  1. var head = createList(5);
  2. console.log('before', JSON.stringify(head));
  3. head = reverseBetween(head, 1, 3);
  4. console.log('after', JSON.stringify(head));
  6. // 打印结果:
  7. // before {"val":0,"next":{"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":5,"next":"none"}}}}}}
  8. // after {"val":0,"next":{"val":3,"next":{"val":2,"next":{"val":1,"next":{"val":4,"next":{"val":5,"next":"none"}}}}}}