leetcode with python:83. Remove Duplicates from Sorted List

题目:

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 = nextclass 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 = nextclass 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%)

那我们下题见