題目:

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

給定一個sorted linked list,消除所有重複的值再回傳
ex:input:[1,1,2,3,3]=>output: [1,2,3]

這題我做了兩個不太一樣的解法,先說第一個

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head: #linked list長度為0直接回傳
            return head
            
        ans=head #紀錄要回傳的head
        
        while head.next:
            if head.val==head.next.val:
                head.next=head.next.next
            else:
                head=head.next
                
        return ans

直到下一項是None為止
如果下一項的值和自己一樣,就將next接到下下項(即跳過下一項,將其排除在linked list外)
若不一樣,則往下一項移動
結束後linked list就會變成我們要的型態
最後執行時間34ms(faster than 99.48%)

第二種方法用了類似1.法二邊遍歷邊紀錄的手法

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
            
        s=set()
        ll=ListNode()
        ans=ll
        while head:
            if head.val not in s:
                s.add(head.val)
                ll.next=ListNode(head.val)
                ll=ll.next
            head=head.next
                
        return ans.next

建立一個set,當遍歷linked list時遇到沒遇過的值就寫入,並將該值加入新的linked list
遍歷完畢獲得的新linked list就是我們要return的東西
最後執行時間39ms(faster than 96.92%)

那我們下題見