跳至主要內容

0083. 删除排序链表中的重复元素

ITCharge大约 1 分钟

0083. 删除排序链表中的重复元素open in new window

  • 标签:链表
  • 难度:简单

题目链接

题目大意

描述:给定一个已排序的链表的头 headhead

要求:删除所有重复的元素,使每个元素只出现一次。返回已排序的链表。

说明

  • 链表中节点数目在范围 [0,300][0, 300] 内。
  • 100Node.val100-100 \le Node.val \le 100
  • 题目数据保证链表已经按升序排列。

示例

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

解题思路

思路 1:遍历

  • 使用指针 currcurr 遍历链表,先将 headhead 保存到 currcurr 指针。
  • 判断当前元素的值和当前元素下一个节点元素值是否相等。
  • 如果相等,则让当前指针指向当前指针下两个节点。
  • 否则,让 currcurr 继续向后遍历。
  • 遍历完之后返回头节点 headhead

思路 1:遍历代码

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head == None:
            return head

        curr = head
        while curr.next:
            if curr.val == curr.next.val:
                curr.next = curr.next.next
            else:
                curr = curr.next
        return head

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)。其中 nn 为链表长度。
  • 空间复杂度O(1)O(1)