LeetCode题目（Python实现）：删除排序链表中的重复元素

偏执的太偏执、 2023-07-11 11:02 26阅读 0赞

文章目录

  • 题目
    • 自己的想法
      • 算法实现
      • 执行结果
      • 复杂度分析
    • 双指针法
      • 执行结果
      • 复杂度分析
    • 小结

题目

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

示例1 :

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

示例2 :

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

自己的想法

算法实现

  1. class Solution:
  2.     def deleteDuplicates(self, head: ListNode) -> ListNode:
  3.         if head is None or head.next is None:
  4.             return head
  5.         cur = head
  6.         while cur.next is not None:
  7.             if cur.val != cur.next.val:
  8.                 cur = cur.next
  9.                 continue
  10.             else:
  11.                 bef = cur
  12.                 while cur.next is not None and cur.val == cur.next.val:
  13.                     cur = cur.next
  14.                 bef.next = None if cur.next is None else cur.next
  15.         return head

执行结果

执行结果 : 通过
执行用时 : 44 ms, 在所有 Python3 提交中击败了72.22%的用户
内存消耗 : 13.5 MB, 在所有 Python3 提交中击败了18.15%的用户
在这里插入图片描述

复杂度分析

  • 时间复杂度：O(n)，我们遍历了包含有 n 个元素的链表一次。
  • 空间复杂度：O(1)，需要额外的常数级空间。

双指针法

  1. class Solution:
  2.     def deleteDuplicates(self, head: ListNode) -> ListNode:
  3.         if head is None or head.next is None:
  4.             return head
  5.         slow = head
  6.         fast = head.next
  7.         while fast is not None:
  8.             if slow.val != fast.val:
  9.                 slow = slow.next
  10.                 slow.val = fast.val
  11.             fast = fast.next
  12.         slow.next = None
  13.         return head

执行结果

在这里插入图片描述

复杂度分析

  • 时间复杂度：O(n)，
    我们只遍历了包含有 n 个元素的链表一次。
  • 空间复杂度：O(1)

小结

先按照自己的想法设计，通过去掉重复的节点来实现。

之后看了双指针法，自己按照思路写了出来，算法快了不少。

发表评论

表情：
评论列表 （有 0 条评论，26人围观）

还没有评论，来说两句吧...

相关阅读