Splitting a Linked List: Separating and Rejoining with Two Dummy Nodes

Table of Contents

Problem Description Solution Approach Core Idea: Two-Dummy Separation Algorithm Steps Code Implementation Illustrated Process Complexity Analysis Key Points Extended Thinking

883 words

4 minutes

Splitting a Linked List: Separating and Rejoining with Two Dummy Nodes

2026-08-10

Algorithms

Linked List

/

Two Pointers

/

Partition

/

C

/

C++

/

JavaScript

Problem Description#

Given a linked list and a specific value x, rearrange the linked list so that all nodes less than x appear before nodes greater than or equal to x. At the same time, preserve the original relative order of the nodes within each of the two parts.

1
Input: head = 1→4→3→2→5→2, x = 3
2
Output: 1→2→2→4→3→5
3
Explanation: Less than 3: 1, 2, 2 (preserve original order)
4
      Greater than or equal to 3: 4, 3, 5 (preserve original order)

Solution Approach#

Core Idea: Two-Dummy Separation#

The intuitive idea is to create two new linked lists—one holding the “small values” and one holding the “large values”—and while traversing the original linked list, assign each node to the corresponding list. After the traversal is complete, connect the tail of the small-value list to the head of the large-value list.

But directly manipulating the “head pointer of the new list” runs into the boundary problem of “who is the first node.” So we use two dummy head nodes to manage the two chains separately.

Algorithm Steps#

Create two dummy head nodes smallDummy and largeDummy
Use tail pointers small and large to maintain the two linked lists respectively
Traverse the original linked list, and assign each node to the corresponding list based on how its value compares with x
After the traversal ends, connect the large list to the tail of the small list
Key: Set large.next to null, otherwise a cycle may form
Return smallDummy.next

Why must large.next = null be set? The last node of the large-value list may originally point to a large-value node. If it is not disconnected, after concatenation the end of the list may point to an old node and form a cycle.

Code Implementation#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct ListNode {
5
    int val;
6
    struct ListNode *next;
7
} ListNode;
8

9
ListNode* partition(ListNode* head, int x) {
10
    // Create two dummy virtual head nodes
11
    ListNode smallDummy, largeDummy;
12
    smallDummy.next = NULL;
13
    largeDummy.next = NULL;
14
    ListNode *small = &smallDummy;
15
    ListNode *large = &largeDummy;
16

17
    // Traverse the original linked list and separate the nodes
18
    ListNode *curr = head;
19
    while (curr) {
20
        if (curr->val < x) {
21
            small->next = curr;
22
            small = small->next;
23
        } else {
24
            large->next = curr;
25
            large = large->next;
26
        }
27
        curr = curr->next;
28
    }
29

30
    // Concatenate the two linked lists
31
    small->next = largeDummy.next;
32
    // Disconnect the end of the larger-value linked list to prevent a cycle
33
    large->next = NULL;
34

35
    return smallDummy.next;
36
}

1
struct ListNode {
2
    int val;
3
    ListNode *next;
4
    ListNode() : val(0), next(nullptr) {}
5
    ListNode(int x) : val(x), next(nullptr) {}
6
    ListNode(int x, ListNode *next) : val(x), next(next) {}
7
};
8

9
class Solution {
10
public:
11
    ListNode* partition(ListNode* head, int x) {
12
        // Create two dummy virtual head nodes
13
        ListNode smallDummy(0), largeDummy(0);
14
        ListNode *small = &smallDummy;
15
        ListNode *large = &largeDummy;
16

17
        // Traverse the original linked list and separate the nodes
18
        ListNode *curr = head;
19
        while (curr) {
20
            if (curr->val < x) {
21
                small->next = curr;
22
                small = small->next;
23
            } else {
24
                large->next = curr;
25
                large = large->next;
26
            }
27
            curr = curr->next;
28
        }
29

30
        // Concatenate the two linked lists
31
        small->next = largeDummy.next;
32
        // Disconnect the end of the larger-value linked list to prevent a cycle
33
        large->next = nullptr;
34

35
        return smallDummy.next;
36
    }
37
};

1
class ListNode {
2
    constructor(val, next) {
3
        this.val = (val === undefined ? 0 : val);
4
        this.next = (next === undefined ? null : next);
5
    }
6
}
7

8
function partition(head, x) {
9
    // Create two dummy virtual head nodes
10
    const smallDummy = new ListNode(0);
11
    const largeDummy = new ListNode(0);
12
    let small = smallDummy;
13
    let large = largeDummy;
14

15
    // Traverse the original linked list and separate the nodes
16
    let curr = head;
17
    while (curr) {
18
        if (curr.val < x) {
19
            small.next = curr;
20
            small = small.next;
21
        } else {
22
            large.next = curr;
23
            large = large.next;
24
        }
25
        curr = curr.next;
26
    }
27

28
    // Concatenate the two linked lists
29
    small.next = largeDummy.next;
30
    // Disconnect the end of the larger-value linked list to prevent a cycle
31
    large.next = null;
32

33
    return smallDummy.next;
34
}

Illustrated Process#

1
Input: head = 1→4→3→2→5→2, x = 3
2

3
Initial state:
4
smallDummy → ?
5
largeDummy → ?
6

7
Step 1: curr=1, 1<3 → put into small
8
smallDummy → 1
9
largeDummy → ?
10

11
Step 2: curr=4, 4≥3 → put into large
12
smallDummy → 1
13
largeDummy → 4
14

15
Step 3: curr=3, 3≥3 → put into large
16
smallDummy → 1
17
largeDummy → 4→3
18

19
Step 4: curr=2, 2<3 → put into small
20
smallDummy → 1→2
21
largeDummy → 4→3
22

23
Step 5: curr=5, 5≥3 → put into large
24
smallDummy → 1→2
25
largeDummy → 4→3→5
26

27
Step 6: curr=2, 2<3 → put into small
28
smallDummy → 1→2→2
29
largeDummy → 4→3→5
30

31
Concatenate and break the end of large:
32
Result: 1→2→2→4→3→5

Complexity Analysis#

Dimension	Analysis
Time Complexity	O(n) — traverse the linked list once
Space Complexity	O(1) — only a few pointers are used, reorganizing in place

Key Points#

Two dummy nodes each manage one part: maintain the small-value chain and the large-value chain separately, making the code logic clear
The end of large must be disconnected: large->next = null is the key step to prevent a cycle; forgetting this line in an interview will cause a serious bug
Preserve relative order: because nodes are traversed in order and appended to the tail, the internal order of the two parts naturally remains unchanged

Extended Thinking#

If the problem did not require preserving relative order, could a more concise method be used? (Direct swapping or in-place adjustment)
If the requirement were “nodes greater than x first, nodes less than x after,” how would you modify it?