86.md

86 Partition List

Description

link

---

Solution

set two point to record small and large numbers, concact them.

---

Code

O(n), O(n)

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

class Solution:
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        small = bs = ListNode(0)
        large = bl = ListNode(0)
        
        while head:
            if head.val < x:
                small.next = ListNode(head.val)
                small = small.next
            else:
                large.next = ListNode(head.val)
                large = large.next
            head = head.next
        
        small.next = bl.next
        return bs.next