卖萌的弱渣

I am stupid, I am hungry.

Partition List

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,

Given 1->4->3->2->5->2->null and x = 3,

return 1->2->2->4->3->5->null.

Solution

  • Time: O(N)
  • Two new list to contain node smaller than x and larger than x
  • Connect two list
(Partition-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
32
33
34
35
36
37

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of linked list.
    @param x: an integer
    @return: a ListNode
    """
    def partition(self, head, x):
        # write your code here
        if head == None or head.next == None:
            return head

        dummy = ListNode(0,None)
        left_list = dummy
        dummy2 = ListNode(0,None)
        right_list = dummy2

        while head != None:
            if head.val < x:
                left_list.next = head
                left_list = left_list.next
            else:
                right_list.next = head
                right_list = right_list.next
            head = head.next
        # connect left_list and right_list
        left_list.next = dummy2.next
        # terminate the right list
        right_list.next = None
        return dummy.next