LeetCode-82.删除排序链表中的重复元素-ii

haiweilian2021-03-10算法LeetCode

题目描述

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

示例 1：

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

示例 2：

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

解法一

因为可能删除头节点，需要一个哨兵节点。然后需要两个指针，pre 用来定位相同节点的开头前一个指针，cur 用来查找相同节点的结尾

因为删除重复元素时有可能需要删除第一个，首先我们要新建一个哨兵节点。
然后需要两个指针，命名 pre 为前一个指针，cur 为当前指针，因为删除链表需要找到当前节点的前一个节点和后一个节点，所以都用 next.val 来比较。
如果 pre.next.val 和 cur.next.val 不相同就不需要删除，那么都往后走一位继续下一个判断。
如果 pre.next.val 和 cur.next.val 相同，那么 cur 继续往后走 pre 不动，直到找到不相同的。
最后 pre.next 和 cur.next 之间的就是相同的节点删除掉。

举例 1->2->2->3->3->4 的运行步骤。

初始的时候 pre = -1->1->2->2->3->3->4(-1为哨兵节点)、cur = 1->2->2->3->3->4。
第一次判断 pre.next.val = 1 和 cur.next.val = 2 不相等。都往后走一位结果为。pre = 1->2->2->3->3->4 、cur = 2->2->3->3->4。
第二次判断 pre.next.val = 2 和 cur.next.val = 2 相等。pre 不动。cur 继续往后走。
第三次判断 pre.next.val = 2 和 cur.next.val = 3 不相等。让 pre.next = cur.next 这样就删除了相同的 2。
继续下一轮的判断。

代码实现

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
  // 可能要删除第一个，所以要定义一个哨兵节点。
  let ret = { next: head };
  let pre = ret;
  let cur = head;

  while (cur && cur.next) {
    // 如果上个节点和下个节点不相等，都往后移动一位。
    if (cur.next.val != pre.next.val) {
      cur = cur.next;
      pre = pre.next;
    } else {
      // 如果相等，连续查找相等的值，这样可以一次性跳过。
      while (cur && cur.next && cur.next.val === pre.next.val) {
        cur = cur.next;
      }
      // 把相同的节点跳过，继续下次查找
      pre.next = cur.next;
      cur = cur.next;
    }
  }

  return ret.next;
};

// ===================================================================
// ========================== @test ==================================
// ===================================================================
let ListNode = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 2,
      next: {
        val: 3,
        next: {
          val: 3,
          next: {
            val: 4,
            next: null,
          },
        },
      },
    },
  },
};

function print(head) {
  let cur = head;
  let link = [];
  while (cur) {
    link.push(cur.val);
    cur = cur.next;
  }
  return `长度为 ${link.length} : 值为 ${link.join("->")}`;
}

console.log(print(deleteDuplicates(ListNode))); // 长度为 2 : 值为 1->4

总结

链表一共打卡了五篇，最后来一个对链表认知的总结。

抽象概念：链表代表了一种唯一指向思想

链表的查询

查询链表常用 while 循环。结束条件可能为 cur && cur.next 查询到末位，或者等于某个值 cur.val === cur.next.val。

链表的删除

删除链表都需要从上一个节点开始操作，因为要删除必须改变指针域，如 cur.next = cur.next.next。

哨兵节点

当不方便操作头节点的时候需要用到哨兵节点，如删除节点需要从上一个节点开始操作。

链表引用

链表是通过指针引用的，列如从原始链表取出一个节点，现在改变这个节点那么原始链表的节点也会改变。为什么说这个呢，因为这个引用关系有时非常绕，容易忽略这个问题。也要善用这个特性。
断开指针引用就用 cur.next = null。

LeetCode-82.删除排序链表中的重复元素-ii

题目描述

解法一

总结

ON THIS PAGE