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

83题的改进，出现的重复数字都要去除掉，利用双指针解决。

题目

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

示例

示例 1:

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

示例 2:

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

考察知识点

链表

核心思想

  • 逐个判断，设置 pre_p 指向出现重复数字之前的一个节点，双指针（快慢）思想。
1
2
3
4
5
6
7
8
9
10
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
     ^    ^
   pre_p  p
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
     ^         ^
   pre_p       p
pre_p = p.next
1 -> 2 -> 4 -> 4 -> 5
     ^    ^
   pre_p  p
  • 设置 is_pure = True，防止全是一个数字的情况 [1, 1, 1]，return None if is_pure else dummy.next 。
  • 最终 return 之前，做个判定，防止结尾为重复数字的情况 [1, 2, 2]。
1
2
if last == p.val: 
	pre_p.next = p.next

Python版本

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
from typing import List

class ListNode():
    def __init__(self, val):
        self.val = val
        self.next = None

    def __str__(self):
        return str(self.val)


def createList(value_list: list) -> ListNode:
    """
    Create Linked List based on list
    :param value_list: list
    :return: NodeList
    """
    _len = len(value_list)
    if _len == 0:
        return None
    if _len == 1:
        return ListNode(value_list[0])
    else:
        root = ListNode(value_list[0])
        tmp = root
        for i in range(1, _len):
            tmp.next = ListNode(value_list[i])  # 声明当前节点，再把当前节点与前面节点联系在一起。
            tmp = tmp.next  # 更新tmp为下一个节点
    return root # 返回根节点


def printList(head: ListNode):
    """
    Print single node one by one in linked list
    :param head: ListNode
    :return: None
    """
    p = head
    while p != None:
        # print()
        print(p)  # 由于有ListNode实现了__str__函数 就不用调用p.val来获取节点值了
        p = p.next


def listLength(head: ListNode) -> int:
    """
    Get the length of linked list
    :param head: ListNode
    :return: int
    """
    count = 0
    p = head
    while p != None:
        count += 1
        p = p.next
    return count

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:  return None
        if head and not head.next: return head
        is_pure = True
        dummy = ListNode(None)  # 声明哑结点
        dummy.next = head  # head肯定不会变
        p = head
        last = None
        pre_p = dummy
        while p and p.next:
            if p.val == p.next.val:  # 出现重复数字
                p.next = p.next.next
                last = p.val
            elif p.val == last:  # 重复数字结束
                pre_p.next = p.next
                p = p.next
                is_pure = False
            else:  # 正常情况
                pre_p = p
                p = p.next
                is_pure = False
        
        if last == p.val:  # 防止结尾为重复数字的情况 [1, 2, 2]
            pre_p.next = p.next

        return None if is_pure else dummy.next  # 防止全是一个数字的情况 [1, 1, 1]


Input = [[1, 2, 3, 4, 4, 5, 5], [1,2,2], [1,2], [1], [2, 2, 2], [1,1], [1, 1, 2, 2, 3, 4, 5], [1, 2, 3, 3, 4, 4, 5], [1, 1, 1, 2, 3]]
Answer = [[1, 2, 3], [1], [1,2], [1], [], [], [3, 4, 5], [1, 2, 5], [2, 3]]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        input_head = createList(Input[i])
        reslut = solution.deleteDuplicates(input_head)
        print(printList(reslut))
        print(Answer[i])

时间复杂度：\(O(n)\)，因为列表中的每个结点都检查一次以确定它是否重复，所以总运行时间为 \(O(n)\)，其中 \(n\) 是列表中的结点数。
空间复杂度：\(O(1)\)，没有使用额外的非常数空间。
执行用时 :32 ms, 在所有 Python3 提交中击败了99.32%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.06%的用户