# 算法 | 链表的处理-链表的合并及删除

一直在思考，一直在尝试，什么样的学习方式是效率最高的。猛然发现，更多的时间花在了思考上面，实际投入到学习的时间少之又少。说来惭愧，学习规划做了一个又一个，好像全部完成的没有一个。总是想要给自己的学习计划做加法，现在我想做减法，给自己降低标准，或许计划更容易完成。

目前想做一个算法刷题系列的文章，每日指定一个系列的算法题目练习。说到算法，其实学了好几次，每次都没有深入学习，而且学了一段时间就忘了。所以目前要做到的写一些文章，希望能写的更清晰明了，写完后愿意在空闲时间也拿出来看一看的那种文章。

我觉得最好的学习方式是反复记忆，甚至变成肌肉记忆，我想尝试的学习方法正是如此，写精炼的文章，然后反复看，反复思考。

本文有些理念来自于修言大佬的小册前端算法与数据结构面试：底层逻辑解读与大厂真题训练 (opens new window) 感兴趣的可以购买看看

言归正传，今天想要学习的是算法 | 链表的处理-链表的合并及删除。

# 链表基础简述

链表和数组相似，它们都是有序的列表、都是线性结构（有且仅有一个前驱、有且仅有一个后继）。不同点在于，链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的。

# 链表的结构

在链表中，每一个结点的结构都包括了两部分的内容：数据域和指针域。

{
    // 数据域
    val: 1,
    // 指针域，指向下一个结点
    next: {
        val:2,
        next: ...
    }
}

# 链表的创建

function ListNode(val) {
    this.val = val;
    this.next = null;
}
const node = new ListNode(1)  
node.next = new ListNode(2)

# dummy结点

由于后文题解常用到dummy 结点，此处重点介绍下dummy结点的概念。

要想访问链表中的任何一个元素，我们都得从起点结点开始，逐个访问 next，一直访问到目标结点为止。为了确保起点结点是可抵达的，我们有时会设定一个 head 指针来专门指向链表的开始位置，dummy结点就登场了。

dummy 结点是人为制造出来的第一个结点的前驱结点，这样链表中所有的结点都能确保有一个前驱结点，也就都能够用同样的逻辑来处理了。dummy 结点能够帮助我们降低链表处理过程的复杂度，处理链表时，不设 dummy 结点思路可能会打不开；设了 dummy 结点的话，就算不一定用得上，也不会出错。

题外话： dummy译为 n.仿制品; 沉默寡言的人; 笨蛋，蠢货; 挂名代表，傀儡 adj.假的; 摆样子的，做样品的; 挂名的; 虚设的所以可以看出dummy只是一个挂名代表，辅助结点，辅助我们能够访问到所有的结点

# 链表的题目分类

链表的题目大致可以分为三类：

链表的处理: 合并、删除(重点)----今天学习的内容
链表的反转及其衍生题目
链表成环问题及其衍生题目

# 链表的合并

任意两结点间插入一个新结点这种类型的增加操作，是链表中的重点之一。需要变更的是前驱结点和目标结点的 next 指针指向

链表形态形如：node1->node2，如果要将node3插入其中形成 node1->node3->node2

const node3 = new ListNode(3)     
// 1. 把目标结点的 next 指针指向后置结点
node3.next = node1.next
// 2. 将前驱结点的 next 指针指向目标结点
node1.next = node3

# 真题应用

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

# 解题思路

中心思想——处理链表的本质，是处理链表结点之间的指针关系。
合并为一个链表，我们恰当地补齐双方之间结点 next 指针的指向关系，就能达到目的
类似穿针引线，现在线有了，缺的是一根针
针每次钻进扣子眼儿之前，要先比较一下它眼前的两个扣子，选择其中值较小的那个，优先把它串进去。一次串一个，直到所有的扣子都被串进一条线为止
还要考虑两个链表长度不等的情况：若其中一个链表已经完全被串进新链表里了，而另一个链表还有剩余结点，考虑到该链表本身就是有序的，我们可以直接把它整个拼到目标链表的尾部。

# 题解

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists = function (l1, l2) {
  // 定义头结点，确保链表可以被访问到
  let head = new ListNode();
  // cur 这里就是咱们那根“针”
  let cur = head;

  // “针”开始在 l1 和 l2 间穿梭了
  while (l1 && l2) {
    // 如果 l1 的结点值较小
    if (l1.val <= l2.val) {
      // 先串起 l1 的结点
      cur.next = l1;
      // l1 指针向前一步
      l1 = l1.next;
    } else {
      // l2 较小时，串起 l2 结点
      cur.next = l2;
      // l2 向前一步
      l2 = l2.next;
    }

    // “针”在串起一个结点后，也会往前一步
    cur = cur.next;
  }

  // 处理链表不等长的情况
  cur.next = l1 !== null ? l1 : l2;
  // 返回起始结点
  return head.next;
};

# 题解笔记

head 作为线，cur 作为针
cur.next 的改动会因为引用关系改变 head 的 next
cur = cur.next 向前移动一步的过程可以一步一步改变 head 的 next
处理链表不等长的情况

# 删除

在涉及链表删除操作的题目中，重点不是定位目标结点，而是定位目标结点的前驱结点。

# 真题应用

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3

# 解题思路

需要删除的目标结点的前驱结点 next 指针往后指一格

# 题解

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const deleteDuplicates = function (head) {
  // 设定 cur 指针，初始位置为链表第一个结点
  let cur = head;
  // 遍历链表
  while (cur != null && cur.next != null) {
    // 若当前结点和它后面一个结点值相等（重复）
    if (cur.val === cur.next.val) {
      // 删除靠后的那个结点（去重）
      cur.next = cur.next.next;
    } else {
      // 若不重复，继续遍历
      cur = cur.next;
    }
  }
  return head;
};

# 题解笔记

while 循环判断条件：当前节点和下个节点不为空不然继续判断也没意义
当前节点和下个节点值比较：cur.val === cur.next.val
继续往下遍历的方法：cur = cur.next

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

# 真题应用

给定一个排序链表，删除所有含有重复数字的结点，只保留原始链表中没有重复出现的数字。输入: 1->2->3->3->4->4->5 输出: 1->2->5 示例 2: 输入: 1->1->1->2->3 输出: 2->3

# 解题思路

链表的第一个结点，没有前驱结点，可以用 dummy 结点来解决这个问题。重复一遍：dummy 结点是人为制造出来的第一个结点的前驱结点，这样链表中所有的结点都能确保有一个前驱结点，也就都能够用同样的逻辑来处理了。dummy 结点能够帮助我们降低链表处理过程的复杂度，处理链表时，不设 dummy 结点思路可能会打不开；设了 dummy 结点的话，就算不一定用得上，也不会出错。
由于重复的结点可能不止一个两个，我们这里需要用一个 while 循环来反复地进行重复结点的判断和删除操作。

# 题解

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const deleteDuplicates = function (head) {
  // 极端情况：0个或1个结点，则不会重复，直接返回
  if (!head || !head.next) {
    return head;
  }
  // dummy 登场
  let dummy = new ListNode();
  // dummy 永远指向头结点
  dummy.next = head;
  // cur 从 dummy 开始遍历
  let cur = dummy;
  // 当 cur 的后面有至少两个结点时
  while (cur.next && cur.next.next) {
    // 对 cur 后面的两个结点进行比较
    if (cur.next.val === cur.next.next.val) {
      // 若值重复，则记下这个值
      let val = cur.next.val;
      // 反复地排查后面的元素是否存在多次重复该值的情况
      while (cur.next && cur.next.val === val) {
        // 若有，则删除
        cur.next = cur.next.next;
      }
    } else {
      // 若不重复，则正常遍历
      cur = cur.next;
    }
  }
  // 返回链表的起始结点
  return dummy.next;
};

← 链表基础时间复杂度和空间复杂度 →