参考资料
练习题 icon lost
交流讨论
笔记
img lost

题目

82. 删除排序链表中的重复元素 II
存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1:

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

示例 2:

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

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

解题思路1

  • 迭代。
  • 判断前后两个节点是否相等,若相等,则需要利用函数把节点去掉,返回self.deleteDuplicates(pop);若不相等,则正常返回就可以,返回head.next

Code

# 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 or not head.next:
            return head
        if head.val != head.next.val:
            head.next = self.deleteDuplicates(head.next)
        else:
            pop = head.next
            while pop and head.val == pop.val:
                pop = pop.next
            return self.deleteDuplicates(pop)
        return head

运行结果


------------------

解题思路2

  • 双指针。
  • 核心思路和迭代的思路是一样的,首先设立两个指针,当遇到重复的,第二个指针继续后移,直到碰到不同的元素为止,这时第一个指针的下一个元素就是第二个指针的下一个元素。

Code

# 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 or not head.next: return head
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        cur = head
        while cur:
            while cur.next and cur.val == cur.next.val:
                cur = cur.next
            if pre.next == cur:
                pre = pre.next
            else:
                pre.next = cur.next
            cur = cur.next
        return dummy.next

运行结果

资料来源 LeetCode:82. 删除排序链表中的重复元素 II————中等
博客作者 Kinght_123
前往答题
我的笔记