algoadvance

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.

For example:

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

Clarifying Questions

  1. What should we do with equal values to x?
    • We should place them in the part of the list that contains the nodes greater than or equal to x.
  2. Are there any constraints on the values in the list?
    • The values are generally within the range of typical integer values.
  3. How do we handle an empty list?
    • Simply return an empty list.

Strategy

We will use two separate lists (or linked lists) to partition the given linked list:

We will maintain two pointers for each partitioned list (before_head, before_tail and after_head, after_tail) to facilitate efficient appending.

Steps:

  1. Traverse the original list.
  2. Append nodes to either the before list or the after list based on the node’s value.
  3. Combine the two lists by setting the next pointer of the last node of the before list to the first node of the after list.
  4. The head of the before list will be the new head of the modified list.

Code

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

def partition(head: ListNode, x: int) -> ListNode:
    if not head:
        return head
    
    before_head = ListNode(0)
    before_tail = before_head
    after_head = ListNode(0)
    after_tail = after_head

    current = head
    while current:
        if current.val < x:
            before_tail.next = current
            before_tail = before_tail.next
        else:
            after_tail.next = current
            after_tail = after_tail.next
        current = current.next

    # Terminate `after` list to prevent potential cycles
    after_tail.next = None

    # Combine partitioned lists
    before_tail.next = after_head.next
    
    return before_head.next

Time Complexity

The solution traverses the list once to partition it, which results in a time complexity of O(n), where n is the number of nodes in the linked list. The space complexity is O(1) excluding the space needed for the output linked list, since we are only using a fixed number of additional pointers.

Try our interview co-pilot at AlgoAdvance.com