链表的应用

链表的合并

真题描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。

// 迭代
function mergeList(l1, l2) {
  const newHead = new ListNode(-1);
  const pre = newHead;
  while (l1 && l2) {
    if (l1.value < l2.value) {
      pre.next = l1;
      l1 = l1.next;
    } else {
      pre.next = l2;
      l2 = l2.next;
    }
    pre = pre.next
  }
  pre.next = l1 === null ? l2 : l1;
  return newHead.next;
}

// 递归

function mergeList(l1, l2) {
  if (l1 === null) return l2;
  if (l2 === null) return l1;
  if (l1.value < l2.value) {
    l1.next = mergeList(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeList(l1, l2.next);
    return l2;
  }
}

链表节点的删除

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

function deleteDuplicates(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;
};

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

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

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

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

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

但是现在，咱们要做的事情变成了把前驱和后继一起删掉，前面两个值为1的结点要一起狗带才行

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

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

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

function deleteDuplicates(head) {
  if (!head || !head.next) {
    return head
  }
  const dummy = new ListNode(-1);
  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;
}