forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
remove-duplicates-from-sorted-list.py
53 lines (45 loc) · 1.33 KB
/
remove-duplicates-from-sorted-list.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from __future__ import print_function
# Time: O(n)
# Space: O(1)
#
# Given a sorted linked list, delete all duplicates such that each element appear only once.
#
# For example,
# Given 1->1->2, return 1->2.
# Given 1->1->2->3->3, return 1->2->3.
#
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur = head
while cur:
runner = cur.next
while runner and runner.val == cur.val:
runner = runner.next
cur.next = runner
cur = runner
return head
def deleteDuplicates2(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head: return head
if head.next:
if head.val == head.next.val:
head = self.deleteDuplicates(head.next)
else:
head.next = self.deleteDuplicates(head.next)
return head
if __name__ == "__main__":
head, head.next, head.next.next = ListNode(1), ListNode(1), ListNode(2)
head.next.next.next, head.next.next.next.next = ListNode(3), ListNode(3)
print(Solution().deleteDuplicates(head))