Partition List

Question

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 and x = 3, return 1->2->2->4->3->5

Tags

• Linked List

Thought

Loop through the whole linked list and divide the nodes into two empty linked list: big and small. After looping this linked list, concatenate these two linked list together.

Code

# 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
        ptr, prev = head, None
        small_head, big_head = ListNode(0), ListNode(0)
        small_tail, big_tail = small_head, big_head
        while ptr:
            if ptr.val < x:
                small_tail.next = ptr
                small_tail = ptr
            else:
                big_tail.next = ptr
                big_tail = ptr
            ptr = ptr.next
        big_tail.next = None
        small_tail.next = big_head.next
        head = small_head.next
        return head