卖萌的弱渣

I am stupid, I am hungry.

Remove Duplicates From Sorted Lists

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example

Given 1->1->2, return 1->2.

Given 1->1->2->3->3, return 1->2->3.

Solution

  • Time: O(n)
(Remove-Duplicates-From-Sorted-List.py) download
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

"""
Definition of ListNode
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: A ListNode
    @return: A ListNode
    """
    def deleteDuplicates(self, head):
        # write your code here
        if head == None or head.next == None:
            return head
        fast_node = head
        slow_node = head


        while fast_node != None:
            if fast_node == slow_node:
                fast_node = fast_node.next
            else:
                slow_node.next = fast_node
                slow_node = fast_node
                fast_node = fast_node.next
       # terminate the result
       # 1->2->3->3->None
       slow_node.next = None
       return head