卖萌的弱渣

I am stupid, I am hungry.

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.

Example

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

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

Solution

(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

#Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        if not head:
            return None
        right = ListNode(-1)
        newhead = ListNode(-1)
        left_head = newhead
        right_head = right
        # assign the nodes into two lists
        while head != None:
            newNode = ListNode(head.val)
            if head.val < x:
                left_head.next = newNode
                left_head = left_head.next
            if head.val >= x:
                right_head.next = newNode
                right_head = right_head.next
            head = head.next
        # connect two lists
        left_head.next = right.next
        return newhead.next