本文题目：

206. 反转链表
25. K 个一组翻转链表

什么是链表

leetcode的做题模板的注释中给了 javascript 的链表的定义：

 // Definition for singly-linked list.
  function ListNode(val, next) {
      this.val = (val===undefined ? 0 : val)
      this.next = (next===undefined ? null : next)
  }

表示每个链表中的节点就是一个对象，对象的val属性用来保存值，next属性用来保存下一个节点的对象引用，相当于指针，最后一个节点要指向null。

node1:{ val:1, next:node2 }
node2:{ val:2, next:node3 }
...
node6:{ val:6, next:null }
-->

当知道一条链表的头节点，通过节点的 next 就可以遍历整条链表。

const node3 = new ListNode(3, null);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(node1);
/* 这里其实就是一个嵌套对象的结构
ListNode {
    val: 1,
    next: ListNode { val: 2, next: ListNode { val: 3, next: null } }
  }  
*/
const tr = (head) => {
  let cur = head;
  while (cur) {
    console.log(cur.val);
    cur = cur.next;
  }
};
tr(node1); // 1 2 3

链表在前端中的应用

原型链通过对象的__proto__属性，连接成原型链。当访问对象的属性或方法不存在这个属性时，那么就会通过原型链查找原型对象上是否存在。

__proto__指向构造函数的prototype(原型对象)，顶端 Object.prototype.proto === null

比如实现instance of,判断 obj 是否是 Type 构造函数的实例

function myInstanceOf(obj, Type) {
  let protoObj = obj.__proto__
  // 只要原型对象存在
  while(protoObj) {
    if (protoObj === Type.prototype) {
      return true
    }
    protoObj = protoObj.__proto__  // 类似链表中遍历 cur = cur.next;
  }
  return false
}

合并两个有序链表

21. 合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。

var mergeTwoLists = function(l1, l2) {
    const prehead = new ListNode(-1);
    let prev = prehead;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }
    // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
    prev.next = l1 === null ? l2 : l1;
    return prehead.next;
};

小技巧：使用一个空节点作为头节点。

反转链表

最高频的一道题就是反转链表这道题了（206. 反转链表）

这道题，就是把整个链表掉头，通过遍历改变每个节点的 next 指向就可以了。

注意两头节点的处理

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev,cur,next;
    cur = head;
    while (cur) {
           next = cur.next; 
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
};

反转链表2（92. 反转链表 II）

请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/kan-qi-lai-chao-jian-dan-de-di-gui-kan-b-d8x1/

困难题K个组翻转链表（25. K 个一组翻转链表）

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

// 反转区间 [a, b) 的元素，注意是左闭右开
const reverse = (a, b) => {
  let pre, cur, next;
  cur = a;
  while (cur != b) {
    next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
  // 返回反转后的头结点
  return pre;
};

var reverseKGroup = function (head, k) {
  if (head == null) {
    return head;
  }
  let a = head, b = head;
  for (let i = 0; i < k; i++) {
    // 不足 k 个，不需要反转，base case
    if (b == null) {
      return head;
    } else {
      b = b.next;
    }
  }
  // 反转前 k 个元素
  let newHead = reverse(a, b);
  a.next = reverseKGroup(b, k); // 递归，看成子问题
  return newHead;
};

参考

一文搞懂单链表的六大解题套路

刷个算法

从反转链表开始

什么是链表

链表在前端中的应用

合并两个有序链表

反转链表

参考