Partition List

Partition List is a classic linked list problem often asked in Apple interviews, focusing on partitioning nodes around a given value using two pointers. It matches LeetCode problem 86 and emphasizes maintaining relative order within partitions.[1][3]

Problem Statement

Given the head of a linked list and an integer x, partition the list so all nodes with values less than x appear before nodes greater than or equal to x. The relative order within each partition must stay the same, and the operation should occur in-place with O(1) extra space.[3][1]

Example 1

Input: head =, x = 3[2][4][5][1][3] Output:[4][5][1][2][3] Explanation: Nodes 1,2,2 (<3) come first in original order, followed by 4,3,5 (≥3) in their original order.[1]

Example 2

Input: head =, x = 2[2][1] Output:[1][2] Explanation: 1 (<2) before 2 (≥2).[3]

Example 3

Input: head =, x = 2[2][3][1] Output: or (both valid due to order preservation).[3][1][2]

Constraints

• Number of nodes: 1 ≤ n ≤ 5 × 10⁴[3]
• Node values: 1 ≤ Node.val ≤ 10⁴
• 0 ≤ x ≤ 10⁴
• List may be empty (head = null returns null).[1]