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

简单的链表去重问题，注意添加特判。
if not head: return None

题目

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例

示例 1:

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

示例 2:

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

考察知识点

链表

核心思想

简单问题，由于输入的列表已排序，因此我们可以通过将结点的值与它之后的结点进行比较来确定它是否为重复结点。如果它是重复的，我们更改当前结点的 next 指针，以便它跳过下一个结点并直接指向下一个结点之后的结点。

c61a88b9fe012a9b85b842f4a12a5310c96b462ea4801e6227fc6a04aa140351-frame_00001.png

图片出处

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
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
        dummy = ListNode(None)  # 声明哑结点
        dummy.next = head  # head肯定不会变
        p = head
        while p and p.next:
            if p.val == p.next.val:
                p.next = p.next.next
            else:
                p = p.next
        return dummy.next

Input = [[1, 1, 2, 2, 3, 4, 5], [1, 2, 3, 3, 4, 4, 5], [1, 1, 1, 2, 3]]
Answer = [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 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)\)，没有使用额外的空间。
执行用时 :48 ms, 在所有 Python3 提交中击败了54.27%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.09%的用户