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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/

博主Github：https://github.com/GDUT-Rp/LeetCode

题目：

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

示例1:

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

示例2:

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

提示：

• -100 <= Node.val <= 100
• 链表中节点数目在范围 [0, 300] 内

解题思路：

方法一：一次遍历

Golang

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    // new head
    newHead := &ListNode{
        Next: head,
    }
    cur := newHead
    for cur.Next != nil && cur.Next.Next != nil {
        if cur.Next.Val == cur.Next.Next.Val {
            x := cur.Next.Val
            // 删除所有值等于x的节点。
            // 一直持续到找到一个值不等于x的节点或者链表结束。
            for cur.Next != nil && cur.Next.Val == x {
                cur.Next = cur.Next.Next
            }
            continue
        }
        cur = cur.Next
    }
    return newHead.Next
}
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

C++

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }
        
        ListNode* dummy = new ListNode(0, head);

        ListNode* cur = dummy;
        while (cur->next && cur->next->next) {
            if (cur->next->val == cur->next->next->val) {
                int x = cur->next->val;
                while (cur->next && cur->next->val == x) {
                    cur->next = cur->next->next;
                }
            }
            else {
                cur = cur->next;
            }
        }

        return dummy->next;
    }
};
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

Java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0, head);

        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

时间复杂度: $O(n)$。

空间复杂度: O(1) 。