结合实际面试中的命题规律，我把这些题目分为以下三类：

  • 链表的处理：合并、删除等（删除操作画个记号，重点中的重点！）
  • 链表的反转及其衍生题目
  • 链表成环问题及其衍生题目

链表的合并

21. 合并两个有序链表

真题描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

做链表处理类问题，大家要把握住一个中心思想——处理链表的本质，是处理链表结点之间的指针关系。
这道题也不例外，我们先来看看处理前两个链表的情况：
链表解题 - 图1
两个链表如果想要合并为一个链表，我们恰当地补齐双方之间结点 next 指针的指向关系，就能达到目的。
如果这么说仍然让你觉得抽象，那么大家不妨把图上的6个结点想象成6个扣子：现在的情况是，6个扣子被分成了两拨，各自由一根线把它们穿起来。而我们的目的是让这六个扣子按照一定的顺序，串到一根线上去。这时候需要咱们做的就是一个穿针引线的活儿，现在线有了，咱缺的是一根针：

链表解题 - 图2

这根针每次钻进扣子眼儿之前，要先比较一下它眼前的两个扣子，选择其中值较小的那个，优先把它串进去。一次串一个，直到所有的扣子都被串进一条线为止（下图中红色箭头表明穿针的过程与方向）：
链表解题 - 图3

同时我们还要考虑 l1 和 l2 两个链表长度不等的情况：若其中一个链表已经完全被串进新链表里了，而另一个链表还有剩余结点，考虑到该链表本身就是有序的，我们可以直接把它整个拼到目标链表的尾部。

  1. function ListNode(val, next) {
  2.     this.val = (val===undefined ? 0 : val)
  3.     this.next = (next===undefined ? null : next)
  4. }
  6. const mergeTwoLists = function (l1, l2) {
  7.     // 定义头结点，确保链表可以被访问到
  8.     let head = new ListNode()
  9.     // cur 这里就是咱们那根“针”
  10.     let cur = head
  11.     // “针”开始在 l1 和 l2 间穿梭了
  12.     while (l1 && l2) {
  13.         // 如果 l1 的结点值较小
  14.         if (l1.val <= l2.val) {
  15.             // 先串起 l1 的结点
  16.             cur.next = l1
  17.             // l1 指针向前一步
  18.             l1 = l1.next
  19.         } else {
  20.             // l2 较小时，串起 l2 结点
  21.             cur.next = l2
  22.             // l2 向前一步
  23.             l2 = l2.next
  24.         }
  25.         // “针”在串起一个结点后，也会往前一步
  26.         cur = cur.next
  27.     }
  28.     // 处理链表不等长的情况
  29.     cur.next = l1 !== null ? l1 : l2
  30.     // 返回起始结点
  31.     return head.next
  32. };

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val) {
  4.  *     this.val = val;
  5.  *     this.next = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} head
  10.  * @param {number} val
  11.  * @return {ListNode}
  12.  */
  13. var deleteNode = function(head, val) {
  14.    let cur = new ListNode(-1);
  15.    cur.next = head;
  16.    let p = cur
  17.    while(p!==null && p.next) {
  18.        if(p.next.val === val) {
  19.           p.next = p.next.next;
  20.        }else{
  21.            p=p.next
  22.        }
  23.    }
  24.    return cur.next
  25. };

链表结点的删除

我们先来看一道基础题目：

真题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3

链表的删除是一个基础且关键的操作，我们在数据结构部分就已经对该操作的编码实现进行过介绍，这里直接复用大家已经学过的删除能力，将需要删除的目标结点的前驱结点 next 指针往后指一格：
链表解题 - 图4
判断两个元素是否重复，由于此处是已排序的链表，我们直接判断前后两个元素值是否相等即可。

删除问题的延伸——dummy 结点登场

真题描述：给定一个排序链表，删除所有含有重复数字的结点，只保留原始链表中 没有重复出现的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3

思路分析

我们先来分析一下这道题和上道题有什么异同哈：相同的地方比较明显，都是删除重复元素。不同的地方在于，楼上我们删到没有重复元素就行了，可以留个“独苗”；但现在，题干要求我们只要一个元素发生了重复，就要把它彻底从链表中干掉，一个不留。

这带来了一个什么问题呢？我们回顾一下前面咱们是怎么做删除的：在遍历的过程中判断当前结点和后继结点之间是否存在值相等的情况，若有，直接对后继结点进行删除：
链表解题 - 图5

这个过程非常自然，为啥？因为咱们要删除某一个目标结点时，必须知道它的前驱结点。在上图中，我们本来就是站在前驱结点的位置，对其后继结点进行删除，只需要将前驱结点的 next 指针往后挪一位就行了。

但是现在，咱们要做的事情变成了把前驱和后继一起删掉，前面两个值为1的结点要一起狗带才行，起始结点直接变成了第三个：
链表解题 - 图6

如果继续沿用刚才的思路，我们会发现完全走不通。因为我们的 cur 指针就是从图中第一个结点出发开始遍历的，无法定位到第一个结点的前驱结点，删除便无法完成。

其实在链表题中，经常会遇到这样的问题：链表的第一个结点，因为没有前驱结点，导致我们面对它无从下手。这时我们就可以用一个 dummy 结点来解决这个问题。

dummy 结点能够帮助我们降低链表处理过程的复杂度，处理链表时，不设 dummy 结点思路可能会打不开；设了 dummy 结点的话，就算不一定用得上，也不会出错。所以笔者个人非常喜欢用 dummy 结点。有心的同学可能也会注意到，在本节的第一题“链表的合并”中，其实也有 dummy 结点的身影。

所谓 dummy 结点，就是咱们人为制造出来的第一个结点的前驱结点，这样链表中所有的结点都能确保有一个前驱结点，也就都能够用同样的逻辑来处理了。

回到这道题上来，我们首先要做的就是定义一个 dummy 结点，指向链表的起始位置：

链表解题 - 图7

这样一来，如果想要删除两个连续重复的值为 1 的结点，我们只需要把 dummy 结点的 next 指针直接指向 2：
链表解题 - 图8
如此一来，就大功告成啦~
注意：由于重复的结点可能不止一个两个，我们这里需要用一个 while 循环来反复地进行重复结点的判断和删除操作。

  1. /**
  2.  * @param {ListNode} head
  3.  * @return {ListNode}
  4.  */
  5. const deleteDuplicates = function(head) {
  6.     // 极端情况：0个或1个结点，则不会重复，直接返回
  7.     if(!head || !head.next) {
  8.         return head
  9.     }
  10.     // dummy 登场
  11.     let dummy = new ListNode() 
  12.     // dummy 永远指向头结点
  13.     dummy.next = head   
  14.     // cur 从 dummy 开始遍历
  15.     let cur = dummy 
  16.     // 当 cur 的后面有至少两个结点时
  17.     while(cur.next && cur.next.next) {
  18.         // 对 cur 后面的两个结点进行比较
  19.         if(cur.next.val === cur.next.next.val) {
  20.             // 若值重复，则记下这个值
  21.             let val = cur.next.val
  22.             // 反复地排查后面的元素是否存在多次重复该值的情况
  23.             while(cur.next && cur.next.val===val) {
  24.                 // 若有，则删除
  25.                 cur.next = cur.next.next 
  26.             }
  27.         } else {
  28.             // 若不重复，则正常遍历
  29.             cur = cur.next
  30.         }
  31.     }
  32.     // 返回链表的起始结点
  33.     return dummy.next;
  34. };