Partition List

Problem: Partition List

The solution is simple. Just use two dummy head, one linking nodes with value smaller than target, the other one linking other nodes, then connect these two lists together.

Code in Python:

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        head1 = tail1 = ListNode(0)
        head2 = tail2 = ListNode(0)
        while head:
            if head.val < x:
                tail1.next = head
                tail1 = tail1.next
            elif head.val >= x:
                tail2.next = head
                tail2 = tail2.next
            head = head.next
        tail1.next, tail2.next = head2.next, None
        return head1.next