Solution Explanation: Partitioning a Linked List

This problem asks us to partition a linked list around a given value x. All nodes with values less than x should come before nodes with values greater than or equal to x. The relative order within each partition must be preserved.

Approach: Two-Pass Simulation

The most efficient approach uses two dummy nodes, one for the "less than" partition (l) and one for the "greater than or equal to" partition (r). We iterate through the input linked list once. For each node:

1. Check the value: If the node's value is less than x, append it to the l list. Otherwise, append it to the r list.

2. Maintain pointers: We use tl and tr to track the tails of the l and r lists respectively, allowing for efficient appending.

After the first pass, we concatenate the l and r lists and return the head of the resulting list. Crucially, we set tr.next to null to terminate the r list before concatenation.

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. We iterate through the list once to build the two partitions and once more to connect them.

• Space Complexity: O(1). We use a constant number of extra variables regardless of the input list size. The space used by the newly created lists is considered part of the output and is not counted in auxiliary space complexity.

Code Implementation (Python)

# 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: Optional[ListNode], x: int) -> Optional[ListNode]:
        l = ListNode()  # Dummy node for less than x
        r = ListNode()  # Dummy node for greater than or equal to x
        tl, tr = l, r  # Pointers to track tails
        while head:
            if head.val < x:
                tl.next = head
                tl = tl.next
            else:
                tr.next = head
                tr = tr.next
            head = head.next
        tr.next = None  # Terminate the r list
        tl.next = r.next  # Concatenate l and r
        return l.next  # Return the head of the new list
 

The implementations in other languages (Java, C++, Go, TypeScript, Rust, Javascript, C#) follow the same logic, with only syntactic differences. They all achieve the same O(n) time and O(1) space complexity.