Cracking The Coding Interview Together – Problem 2.4: Partition

Alright, let’s continue the Cracking the Coding Interview — Together series and tackle another classic linked list problem. As always, we’ll do this the interview way, not the “just jump to code” way.

Take your time with this one. Read slowly. Pause where needed. This problem looks simple on the surface, but it tests how cleanly you think under constraints.

As always, we’ll follow the same structure that you would use in a real interview.

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Partition: Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. If x is contained within the list, the values of x only need to be after the elements less than x. The partition element x can appear anywhere in the right partition; it does not need to sit exactly between the left and right partitions.

Example

Input

3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1
partition = 5

Output (one valid answer)

3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

Important note:
There can be multiple valid outputs. Order is not strictly enforced unless stated.

Analyse the problem statement together

Before thinking about code, let’s slow down and really understand what’s being asked.

We are given:

• A singly linked list
• A pivot value x

Our goal:

• All nodes with values less than x should come before
• All nodes with values greater than or equal to x

What is not required:

• Preserving the original relative order (unless we choose to)
• Placing x exactly in the middle
• Sorting the list

This is not a sorting problem.
This is a partitioning problem.

That distinction matters a lot.

Questions for the interviewer

Before jumping into solutions, this is the moment where you speak up. Interviews are not exams; they are conversations. Clarifying assumptions is a strength, not a weakness.

Here are the questions I would ask:

1. Can the given node ever be the first or last node?
2. Is the linked list singly linked or doubly linked?
3. Are node values unique, or does it not matter?
4. Should the function return anything, or just modify the list?
5. Can the list contain only one or two nodes?

And based on the problem statement, the interviewer would likely answer:

• The node will never be the first or last node
• The list is singly linked
• You only need to modify the list, no return value
• Node values don’t matter for the solution

Good. Now we know exactly what we’re dealing with.

Think about the Solution

Don’t scroll yet.

Take a minute and think:

• How would you explain this to an interviewer?
• Would you move nodes?
• Would you create new lists?
• Would you scan once or multiple times?

There is no rush.
This thinking phase is where interviews are won.

Let’s reason it out step by step, just like you would in a real interview.

We walk through the linked list once.
For each node, we decide:

• Does this node belong to the left side (< x)?
• Or the right side (>= x)?

That’s it.
No sorting. No swapping values. Just classification.

Now comes the design choice:

Option A: Rearrange Nodes In-Place

• More pointer manipulation
• Easy to mess up
• Harder to explain cleanly under pressure

Option B: Build Two Separate Lists

• One list for values < x
• One list for values >= x
• Then stitch them together

This option is:

• Cleaner
• Easier to reason about
• Easier to debug
• Easier to explain

Unless the interviewer explicitly forbids extra pointers, Option B is the smarter choice.

We’ll go with that.

High-Level Algorithm

Here’s the idea in plain English:

1. Create two dummy heads:
   • One for the left partition
   • One for the right partition
2. Traverse the original list node by node
3. If the node’s value is < x, append it to the left list
4. Otherwise, append it to the right list
5. At the end, connect the left list to the right list
6. Return the head of the combined list

Simple. Predictable. Interview-friendly.

Write code and explain

Now let’s translate this idea into code.

Java code

Node Definition (Assumed)

class ListNode {
    int data;
    ListNode next;

    ListNode(int data) {
        this.data = data;
        this.next = null;
    }
}

Partition Function

public static ListNode partition(ListNode head, int x) {
    if (head == null) return null;

    // Dummy heads for left and right partitions
    ListNode leftDummy = new ListNode(0);
    ListNode rightDummy = new ListNode(0);

    ListNode leftTail = leftDummy;
    ListNode rightTail = rightDummy;

    ListNode current = head;

    while (current != null) {
        if (current.data < x) {
            leftTail.next = current;
            leftTail = leftTail.next;
        } else {
            rightTail.next = current;
            rightTail = rightTail.next;
        }
        current = current.next;
    }

    // Important: terminate right list
    rightTail.next = null;

    // Connect left and right partitions
    leftTail.next = rightDummy.next;

    return leftDummy.next;
}

Explain the Code (Like You Would to the Interviewer)

Let’s walk through this calmly.

• We use dummy nodes to avoid edge cases like empty lists.
• leftDummy represents the start of the < x list.
• rightDummy represents the start of the >= x list.
• As we traverse the original list:
  • Each node is attached to one of the two lists.
• We do not create new nodes.
• We only rewire next pointers.
• At the end:
  • We terminate the right list
  • Connect left and right
  • Return the new head

This keeps the logic clean and avoids bugs.

Time & Space Complexity

Time Complexity

• We traverse the list once
• O(n) where n is the number of nodes

Space Complexity

• We use a constant number of pointers
• No new nodes are created
• O(1) extra space

Final Thoughts

This problem isn’t about linked lists.

It’s about:

• Breaking a problem into clean decisions
• Choosing the simplest valid approach
• Writing code that you can explain under stress

If you can talk through this problem clearly, you’re doing well.

As always, I’d strongly encourage you to:

• Re-implement this yourself
• Try a slightly different input
• Explain it out loud, even if you’re alone

That habit pays off more than anything else.

I’ll see you in the next one.
Until then — keep practicing, and keep thinking clearly.