def(self, head, val): """ :type head: ListNode :type val: int :rtype: ListNode """ if head == None: returnNone if head.next == None: returnNoneif head.val == val else head p1 = head while p1 != Noneand p1.next != None: v1 = p1.next.val if v1 == val: p1.next = p1.next.next else: p1 = p1.next # check if first element is same as val if head.val == val: head = head.next # check if last element is same as val if head != Noneand head.val == val: head = head.next return head
Time complexity: O(n) Space complexity: O(1)
use two pointer, fast pointer(pointer) go faster than slow pointer if fast pointer = slow pointer, means duplicates starts keep fast pointer going until it reach a node have different value than slow pointer let slow pointer.next point to that node so duplicate removed
Bext Solution
reduce code size
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def(self, head, val): """ :type head: ListNode :type val: int :rtype: ListNode """ if(head==None):return head dummyHead=ListNode(-1) dummyHead.next=head prev=dummyHead while(head): if(head.val!=val): prev.next = head prev=head head=head.next prev.next=None return dummyHead.next
近期评论