Partition List

MediumLinked Listtwo pointers

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the head of a singly linked list and an integer x. Rearrange the list so that every node whose value is **strictly less than** x comes before every node whose value is **greater than or equal to** x. The relative order of nodes must be preserved inside each of the two groups. For example, if two nodes are both smaller than x, the one that appeared first in the input must still appear first in the output. Return the head of the rearranged list. An empty list stays empty. Aim for O(n) time and O(1) extra space by relinking the existing nodes.

Examples

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Nodes below 3 are 1, 2, 2 (in original order); the rest are 4, 3, 5.
Input: head = [2,1], x = 2
Output: [1,2]
Only 1 is below 2, so it moves to the front.

Constraints

  • 0 <= number of nodes <= 200
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More two pointers problems