We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Partition List

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires rearranging a linked list based on a value x.
  • Two separate lists (or partitions) can be created to hold nodes less than x and nodes greater than or equal to x.
  • After processing all nodes, the two lists can be merged to maintain the required order.
  • The algorithm can be implemented using a single traversal of the linked list.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the linked list, as we traverse the list once. Space Complexity: O(1) - we are using a constant amount of extra space for pointers.

Solution

To solve the problem, we can use two dummy nodes to represent the heads of two partitions: one for nodes less than x and one for nodes greater than or equal to x. As we traverse the linked list, we will append each node to the appropriate partition. Finally, we will connect the two partitions and return the head of the new list.

Code Solutions

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

def partition(head: ListNode, x: int) -> ListNode:
    less_head = ListNode(0)  # Dummy head for less than x
    greater_head = ListNode(0)  # Dummy head for greater or equal to x
    
    less = less_head  # Pointer for less list
    greater = greater_head  # Pointer for greater list
    
    current = head  # Pointer for traversing the original list
    while current:
        if current.val < x:
            less.next = current  # Append to less list
            less = less.next
        else:
            greater.next = current  # Append to greater list
            greater = greater.next
        current = current.next
    
    greater.next = None  # End the greater list
    less.next = greater_head.next  # Connect the two lists
    
    return less_head.next  # Return the head of the new list
← Back to All Questions