83 remove duplicates from sorted list

AC and Best Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def (self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
p1 = head
p2 = head.next
while p2 != None:
if p1.val != p2.val:
p1.next = p2
p1 = p2
p2 = p2.next
if p1 != None:
p1.next = None
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