LeetCode Solutions Blog

Partition List

Number: 86

Difficulty: Medium

Paid? No

Problem Description

Given the head of a linked list and a value x, partition the list such that all nodes with values less than x come before nodes with values greater than or equal to x. The original relative order of the nodes in each partition must be preserved.

Key Insights

Use two separate lists: one for nodes less than x and one for nodes greater than or equal to x.
Create dummy nodes for each list to simplify edge case handling.
Traverse the original list once, partitioning nodes into the two lists.
Connect the two lists at the end to obtain the final partitioned list.

Space and Time Complexity

Time Complexity: O(n) because we traverse the list once.
Space Complexity: O(1) since we only use a constant number of pointers.

Solution

We maintain two dummy head nodes to start the lists for nodes less than x and nodes greater than or equal to x. As we traverse the original list, we append each node to the appropriate list. After the traversal, we link the end of the less-than list to the head of the greater-than or equal list and set the tail of the greater list to None (or null) to avoid forming a cycle. Finally, we return the new head from the less-than list.

Code Solutions

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

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        # Initialize two dummy nodes for less and greater lists
        less_dummy = ListNode(0)
        greater_dummy = ListNode(0)
        less = less_dummy  # pointer for less-than list
        greater = greater_dummy  # pointer for greater or equal list
        
        # Traverse through original list and partition nodes
        while head:
            if head.val < x:
                less.next = head  # add node to less list
                less = less.next  # move pointer forward
            else:
                greater.next = head  # add node to greater list
                greater = greater.next  # move pointer forward
            head = head.next  # advance to the next node in the list
        
        # Terminate the greater list to avoid cycles
        greater.next = None
        # Link the less list with the greater list
        less.next = greater_dummy.next
        
        # Return the start of the new list
        return less_dummy.next