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

发表于 分类于

题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例1

1
2
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例2

1
2
输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

题解

思路：

  1. 给链表前加上表头，方便可能的话删除第一个节点。
  2. 遍历链表，每次比较相邻两个节点，如果遇到了两个相邻结点相同，则新开内循环将这一段所有的相同都遍历过去。
  3. 在step 2中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。
  4. 返回时去掉添加的表头。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func deleteDuplicatesII(_ head: ListNode?) -> ListNode? {
  let res = ListNode(-1)
  res.next = head
  
  var pre: ListNode? = res
  var cur = head
  while cur != nil {
    while cur?.next !== nil && cur!.next!.val == cur!.val {
      cur = cur?.next
    }
    if pre?.next === cur {
      pre = cur
      cur = cur?.next
    } else {
      pre?.next = cur?.next
      cur = cur?.next
    }
  }
  
  return res.next
}