1
# Runtime: 53 ms (Top 53.47%) | Memory: 13.8 MB (Top 76.51%)
2
# Definition for singly-linked list.
3
# class ListNode(object):
4
# def __init__(self, val=0, next=None):
5
# self.val = val
6
# self.next = next
7
class Solution(object):
8
    def partition(self, head, x):
9
        """
10
        :type head: ListNode
11
        :type x: int
12
        :rtype: ListNode
13
        """
14
        lessthan = []
15
        greateql = []
16

17
        while head:
18
            if head.val < x:
19
                lessthan.append(head.val)
20
            else:
21
                greateql.append(head.val)
22
            head = head.next
23

24
        h = res = ListNode()
25

26
        for i in range(len(lessthan)):
27
            res.next = ListNode(lessthan[i])
28
            res = res.next
29
        for i in range(len(greateql)):
30
            res.next = ListNode(greateql[i])
31
            res = res.next
32

33
        return h.next