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

1. 题目

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

示例 1：

img

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

示例 2：

img

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

提示：

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

2. 思路

  • 初始化dummy头指针节点，主要是防止需要移除原有头部，因此需要有一个固定头指针，结果返回为dummy.next
  • 初始化curNode作为当前节点，初始化preNode作为上一个节点
  • 遍历curNode链表，当curNode存在下一个节点并且下一个节点与当前节点值一样，则需要对从当前节点开始值一样的节点进行剔除
  • 剔除后重新循环判断上述条件，如果不一致，则可正常进行遍历，过程中需要实时更新preNode节点
  • 剔除函数传入参数为preNode作为起始判断节点，因为自该节点开始还未出现重复，主要剔除的是该节点的后续重复节点，并且在处理完成后，需要将preNode.next与下一个节点进行串联
  • 完成遍历后，返回dummy.next

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        var dummy = new ListNode(Integer.MAX_VALUE);
        dummy.next = head;
        
        var curNode = dummy;
        ListNode preNode = null;

        while (curNode != null) {
            if (curNode.next != null && curNode.val == curNode.next.val) {
                curNode = removeDuplicateNode(preNode, curNode.val);
                continue;
            }

            preNode = curNode;
            curNode = curNode.next;
        }

        return dummy.next;
    }

    private ListNode removeDuplicateNode(ListNode startNode, int targetVal) {
        var preNode = startNode;
        var curNode = startNode.next;

        while (curNode != null && curNode.val == targetVal) {
            curNode = curNode.next;
        }

        preNode.next = curNode;
        return curNode;
    }
}

4. 复杂度

  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

image-20231003114013425