0086 Partition List

Problem

Given the head of 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.

Examples

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

Analysis

Solution

class Node():
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(A):
    dummy = Node()

    if not A:
        return dummy.next
    
    prev = dummy
    for a in A:
        cur = Node(a)
        prev.next = cur 
        prev = cur
    
    return dummy.next 

def linkedListToList(head):
    res = []
    while head:
        res.append(head.val)
        head = head.next
    return res

def partitionList(head, x):
    dummy1 = Node(0)
    dummy2 = Node(0)
    
    p, p1, p2 = head, dummy1, dummy2
    while p:
        if p.val < x:
            p1.next = p 
            p1 = p1.next 
        else:
            p2.next = p
            p2 = p2.next 
        # both p1 and p2 should have none next pointer after update
        # which means p.next should be none
        temp = p.next
        p.next = None
        # advance 
        p = temp
    
    # combine
    p1.next = dummy2.next

    return dummy1.next 

# test
head = build([1,4,3,2,5,2])
x = 3
newhead = partitionList(head, x)
print(linkedListToList(newhead))

head = build([2, 1])
x = 2
newhead = partitionList(head, x)
print(linkedListToList(newhead))

[1, 2, 2, 4, 3, 5]
[1, 2]