This page looks best with JavaScript enabled

Leetcode 83 Remove Duplicates from Sorted List

題目大意

  • 給一個已經按照 val 排序過的 linked list, 回傳(刪除)去重後的 linked list
  • The number of nodes in the list is in the range [0, 300].

Problem

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

My Solution

基本版

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# 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:
        node = head
        while node:
            while node.next and node.val == node.next.val:
                node.next = node.next.next
            node = node.next
        return head
  • 如果目前與下一個 val 相同,就把目前的 next 指向下下個,重複直到找到 val 不同
  • 重複以上動作,所以有兩個 while

recursive version

1
2
3
4
5
6
7
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head:
            head.next = self.deleteDuplicates(head.next)
            if head.next and head.val == head.next.val:
                return head.next
        return head
  • 如果不是結尾,把下一個丟入 recursion 檢查
  • 判斷檢查過的 linked list 的第一個 node 與現在的 node 兩者 value 是否相同,如果相同,就略過目前的 node

比較

基本版與 recursive版的差別是如果重複的話,基本版會保留前面, recursive版保留後面