链表是一种重要的数据结构，无论是在我们的工作中，还是在我们的面试中都经常出现。 这种数据结构可以用在很多地方，比如内核的消息队列、缓存管理、跳表，B+ 树等。

在面试中面试官非常喜欢考察面试者的链表知识，主要有以下 3 个原因：

• 操作链表需要非常小心，考虑各种边界情况；

• 链表结构简单，但是查找、交换、翻转都非常容易出错；

• 解决链表问题，需要有一定的算法思想，但是又并不太难。在面试过程中，需要你想到解题方法并实现出来，更加考察应试者的工程能力。

一、第一板斧：假头

什么是假头，假头通常也叫作 Dummy Head 或者“哑头”。实际上，就是在链表前面，加上一个额外的结点。此时，存放了 N 个数据的带假头的链表，算上假头一共有 N+1 个结点。

额外的结点不会存放有意义的数据。那么它的作用是什么呢？ 添加假头后，可以省略掉很多空指针的判断。链表的各种操作会变得更加简洁。 比如：

1.1 初始化

初始化一个链表节点，并且让链表的 dummy 和 tail 指针都指向它。

// 初始化 dummy 
const dummy = new ListNode();
// 初始化链表 tail 指针
const tail = dummy;
// 记录链表长度
let length = 0;

注意

• dummy 指针初始化好之后，永远都是静止的，不会在动
• tail 指针在链表发生改变的时候，就需要移动调整

1.2 尾部添加节点

在链表的尾部添加一个节点。在有假头的情况下，是不需要判断 tail 节点是否为空的操作。

function addTail(val) {
  tail.next = new ListNode(val);
  tail = tail.next;
  length++;
}

1.3 头部添加节点

需要插入的新结点为 p，插入之后，新结点 p 会成为第一个有意义的数据节点。通过以下 3 步可以完成头部插入： 新结点 p.next 指向 dummy.next；dummy.next 指向 p；如果原来的 tail 指向 dummy，那么将 tail 指向 p。 由于有 dummy 结点的存在，代码并不会遇到空指针，当链表为空的时候，它依然是可以工作的。

function addHead(val) {
  const p = new ListNode(val);
  p.next = dummy.next;
  dummy.next = p;
  if (tail === dummy) {
    tail = p;
  }
  length++;
}

1.4 查找节点

在查找索引值为 index（假设 index 从 0 开始）的结点时，需要注意，大多数情况下，返回指定结点前面的一个结点 prev 更加有用。

所以查找节点，关键点在于查找前一个节点。 好处有以下两个方面：

• 通过 prev.next 就可以访问到你想要找到的结点，如果没有找到，那么 prev.next 为 null；
• 通过 prev 可以方便完成后续操作，比如在 target 前面 insert 一个新结点，或者将 target 结点从链表中移出去。

function getPrevNode(index) {
  let front = dummy.next;
  let back = dummy;

  for (let i = 0; i < index && front !== null; i++) {
    back = front;
    front = front.next;
  }
  return back;
}

function get(index) {
  if (index < 0 || index >= length) return -1;

  return getPrevNode(index);
}

有了假头的帮助，这段查找代码就非常健壮了，可以处理以下 2 种情况：

• 如果 target 在链表中不存在，此时 prev 返回链表的最后一个结点；
• 如果为空链表（空链表指只有一个假头的链表），此时 prev 指向 dummy。也就是说，返回的 prev 指针总是有效的。

1.5 在指定位置之前插入节点

在指定位置之前插入节点，也就是在指定节点的前一个节点后面挂入一个节点。但是在操作的过程中，需要考虑多种情况：

• 如果 index 大于链表长度，则不会插入结点。
• 如果 index 等于链表的长度，则该结点将附加到链表的末尾。
• 如果 index 小于 0，则在头部插入结点。
• 否则在指定位置前面插入结点

function addAtIndex(index, val) {
  if (index > length) return;
  else if (index === length) addAtTail(val)
  else if (index <=0 ) addAtHead(val)
  else {
    const pre = getPrevNode(index);
    const p = new ListNode(val);
    p.next = pre.next;
    pre.next = p;
    length++;
  }
}

1.6 删除节点

删除节点时，也需要考虑多种情况：

• 如果 index 无效，那么什么也不做；
• 如果 index 有效，那么将这个结点删除。

function deleteAtIndex(index) {
  if (index < 0 || index >= length) return;

  const pre = getPrevNode(index);
  if (tail === pre.next) {
    tail = pre;
  }
  pre.next = pre.next.next;
  length--;
}

二、第二板斧：新链表

做链表的反转、交换等操作时，不建议直接在原来的链表上进行操作。一种可取的思路是，把这些操作想象成要生成新的链表，然后借助这些新的链表，完成原本比较复杂的操作。

2.1 反转链表

简单的反转链表：利用新链表，就非常的简单，不操作原链表。

var reverseList = function(head) {
  const dummy = new ListNode();
  while(head !== null) {
    const temp = head.next;
    head.next = dummy.next
    dummy.next = head;
    head = temp
  }

  return dummy.next;
}

在稍微难一点，给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

var reverseList = function(head, left, right) {
  const dummy = new ListNode(-1);
  dummy.next = head;
  let pre = dummy;

  // 找到需要反转节点的前一个节点
  for (let i = 0; i < right - 1; ++i) {
    pre = pre.next;
  }
 
  // 这里的 cur 节点就是已经需要反转的节点
  let cur = pre.next;
  
  // 开始进行节点反转
  for (let  i = 0; i < right - left; ++i) {
    // 当前节点的下一个节点
    const next = cur.next;
    cur.next = next.next;	
    next.next = pre.next;
    pre.next = next;
  }
  return dummy.next;
}

2.2 删除节点

假头 + 新链表

var removeNode = function(head, val) {
  const dummy = new ListNode(-1);
  let tail = dummy;

  while(head !== null) {
    const next = head.next;
    if (head.val !== val) {
      tail.next = head;
      tail = head;
    }
    head = next;
  }
  tail.next = null
  return dummy.next;
}

三、第三板斧：双指针

双指针，顾名思义就是两个指针在链表上移动。实际上，我们在前面链表的查找中已经使用过双指针了：比如链表中指定位置插入一个新结点，就使用了两个指针，一前一后两个指针在链表上前进。 其实两个指针在链表上前进时，有很多种形式，常见的主要有以下两种：

• 间隔指针：前面的指针先走一步，然后后面的指针再一起走；前面的指针先走 k 步，后面的指针再一起走。
• 快慢指针：两个指针的速度一快一慢前进，比如一个每次走一步，一个每次走两步。

当有偶数个结点，s2 是空指针，此时，s1 位于后半部分指针的头部，因此需要返回s1 的前驱；

当有奇数个结点，s2 是最后一个结点，此时 s1 指针位于前半部分的最后，直接返回 s1即可。

3.1 删除链表的倒数第 N 个结点

一般情况下，有的同学会先统计出整个链表的长度 len, 再去取第 len-k 结点的前驱进行删除。这样需要遍历链表两次，如果只能遍历链表一次。实际上就是在告诉你“用双指针吧”。思路如下：

• 在原链表前面加上 dummy，变成带假头的链表
• front 指针从 dummy 开始，走 k 步，然后停下来
• back 指针指向链表 dummy 假头
• 然后两个指针再一起走
• 当 front 指针指向最后一个结点时，back 指针刚好指向倒数第 k 个结点的前驱。

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode();
    dummy.next = head;
    let front = dummy;
    let back  = dummy;

    while(head !== null) {
       front = front.next;
       if (n === 0) {
           back = back.next;
       } else {
           n--;
       }
       head = head.next;
    }
    back.next = back.next.next;

    return dummy.next;
};

3.2 拆分链表

给定一个链表，需要把链表从中间拆分成长度相等的两半（如果链表长度为奇数，那么拆分之后，前半部分长度更长一点）。关键点在于找到中间节点，当然你可以首先求出链表的长度，然后再利用 getPreNode(len/2) 函数的前驱，再把链表拆分成两半。但是还是只能遍历链表一次。实际上就是在告诉你“用双指针吧”。思路如下：

• 假设链表头在左边，尾巴在右边，两个指针 s1、s2 从链表头开始往右走；
• s1 表示每次只往前走一步，s2 则表示每次只往前走 2 步；
• 在同样的时间内，当 s2 指向链表的末尾，s1 指针便指向链表的中间结点。

function findMiddleNode(head) {
    // 注意这里转化为带假头的链表，免去了空链表的判断
    const dummy = new ListNode();
    dummy.next = head;
    // 注意，假头并不算是链表的一部分，所以这里是从head开始走
    let s2 = head;
    let s1 = head;
    // dummy就是head的前驱，所以pre要指向dummy.
    ListNode pre = dummy;
    // 两个指针开始同时走
    // 因为s2指针每次都要走两步，所以判空需要这样判断。
    while (s2 != null && s2.next != null) {
        pre = s1;
        s1 = s1.next;
        s2 = s2.next.next;
    }
    // 当有偶数个结点的时候，s2是空指针，
    // 此时，s1位于后半部分指针的头部，因此需要返回s1的前驱。
    // 当有奇数个结点的时候，s2是最后一个结点，
    // 此时s1指针位于前半部分的最后，直接返回s1即可。
    return s2 != null ? s1 : pre;
}
function split(head) {
    // 这里获取了链表的中间结点
    let mid = findMiddleNode(head);
    // 拿到链表的中间结点之后，可以得到链表的后半部分的开头
    let back = mid.next;
    // 把链表拆分为两半
    mid.next = null;
    // 返回两个链表的头部
    return { head, back };
}

四、总结

• 第一斧：假头。假头的作用主要是避免关于空链表的判断与讨论，假头还可以用来避免检查前驱结点为空的情况。
• 第二斧：新链表。新链表的引入是为了解决在旧链表中进行原地的交换、插入、删除，把复杂的操作变成在新链表中头部插入或者尾部添加。
• 第三斧：双指针。双指针主要是用于寻找链表中的特定结点，双指针的走法可以一次一步，可以有快有慢，出发点也可以有前有后。

参考