汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

删除排序链表中的重复元素(系列)

发表于 分类于 Valine：
本文字数： 898 阅读时长 ≈ 1 分钟

删除重复元素，保留一个

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        p = head
        q = head.next
        while q:
            if q.val == p.val:
                r = q.next
                p.next = r
                del q
                q = r
            else:
                p = q
                q = q.next
        return head

删除所有重复的元素

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

细节题, 关键点是有可能删除第一个元素，为了方便，一般需要添加一个dummy节点

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        dummy = ListNode(next=head)
        p = dummy
        q = dummy.next
        while q and q.next:
            if q.val == q.next.val:
                last_deleted = q.val
                while q and q.val == last_deleted:
                    r = q.next
                    p.next = r
                    del q
                    q = r
            else:
                p = q
                q = q.next
        return dummy.next
坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------