Partition List Medium 0 attempts
LeetCode ↗

Partition List

Medium Linked List LeetCode

You're given the head of a linked list along with a value x. Rearrange the nodes so every node holding a value less than x appears before every node holding a value greater than or equal to x, keeping the original relative order within each of the two groups.

Input Format
Implement partition(head, x). Inputs below show JavaScript function arguments; there is no stdin parsing. Linked lists use value arrays. The editor passes nodes with val and next properties; [] becomes null.
Output Format
Return the result described in the statement. Returned list heads are displayed as value arrays; a null head is [].

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
head = []
x = 3
Output
[]
Constraints
  • 0 to 200 nodes
  • -100 <= Node.val <= 100
  • -200 <= x <= 200
Test Cases (2)
Case 1
Args: [[1,4,3,2,5,2],3] Expected: [1,2,2,4,3,5]
Case 2
Args: [[],3] Expected: []
Topics
Linked List

Two Lists

javascript
function partition(head, x) {
  const before = {next:null}, after = {next:null};
  let b = before, a = after;
  while (head) {
    if (head.val < x) { b.next = head; b = b.next; }
    else { a.next = head; a = a.next; }
    head = head.next;
  }
  a.next = null; b.next = after.next;
  return before.next;
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript