Problem#
Given a linked list, uniformly shuffle the nodes. What if we want to prioritize space over time?
Examples#
Example 1#
1
2
3
4
5
Input: 1 -> 2 -> 3 -> 4 -> NULL
Output: 3 -> 1 -> 4 -> 2 -> NULL ( one possible shuffle)
Explanation:
The linked list nodes are shuffled randomly while maintaining the linked list structure.
Each permutation should have equal probability of occurring.
Example 2#
1
2
3
4
Input: 5 -> NULL
Output: 5 -> NULL
Explanation:
Single node list remains unchanged as there' s only one possible arrangement.
Example 3#
1
2
3
4
5
6
Input: 1 -> 2 -> NULL
Output: 2 -> 1 -> NULL ( or 1 -> 2 -> NULL)
Explanation:
Two nodes can be arranged in 2 ways with equal probability ( 50 % each):
- Original: 1 -> 2
- Shuffled: 2 -> 1
Example 4#
1
2
3
4
Input: NULL
Output: NULL
Explanation:
Empty list remains empty after shuffling.
Example 5#
1
2
3
4
5
Input: 7 -> 8 -> 9 -> NULL
Output: 9 -> 7 -> 8 -> NULL ( one possible shuffle)
Explanation:
Three nodes can be arranged in 3 ! = 6 different ways.
Each arrangement should have probability 1 / 6.
Solution#
Method 1 - Array-Based Fisher-Yates Shuffle#
Intuition#
The most straightforward approach is to convert the linked list to an array, apply the Fisher-Yates shuffle algorithm for uniform randomness, then reconstruct the linked list. This guarantees perfect uniform distribution but requires O(N) extra space. The Fisher-Yates algorithm ensures each permutation has exactly equal probability.
Approach#
Traverse the linked list and store all node references in an array
Apply Fisher-Yates shuffle algorithm to the array:
For each position i from n-1 down to 1
Generate random index j between 0 and i (inclusive)
Swap elements at positions i and j
Reconstruct the linked list using the shuffled array order
Update next pointers to reflect the new arrangement
Return the new head of the shuffled list
Code#
Cpp
Go
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class ListNode {
public :
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr ) {}
};
class Solution {
public :
ListNode* shuffleList(ListNode* head) {
if (! head || ! head-> next) return head;
// Convert to array
vector< ListNode*> nodes;
ListNode* curr = head;
while (curr) {
nodes.push_back(curr);
curr = curr-> next;
}
// Fisher-Yates shuffle
int n = nodes.size();
for (int i = n - 1 ; i > 0 ; i-- ) {
int j = rand() % (i + 1 );
swap(nodes[i], nodes[j]);
}
// Reconstruct linked list
for (int i = 0 ; i < n - 1 ; i++ ) {
nodes[i]-> next = nodes[i + 1 ];
}
nodes[n - 1 ]-> next = nullptr ;
return nodes[0 ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
type ListNode struct {
Val int
Next * ListNode
}
func shuffleList (head * ListNode ) * ListNode {
if head == nil || head .Next == nil {
return head
}
// Convert to slice
var nodes []* ListNode
curr := head
for curr != nil {
nodes = append(nodes , curr )
curr = curr .Next
}
// Fisher-Yates shuffle
n := len(nodes )
for i := n - 1 ; i > 0 ; i -- {
j := rand .Intn (i + 1 )
nodes [i ], nodes [j ] = nodes [j ], nodes [i ]
}
// Reconstruct linked list
for i := 0 ; i < n - 1 ; i ++ {
nodes [i ].Next = nodes [i + 1 ]
}
nodes [n - 1 ].Next = nil
return nodes [0 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode shuffleList (ListNode head) {
if (head == null || head.next == null ) return head;
// Convert to array
List< ListNode> nodes = new ArrayList<> ();
ListNode curr = head;
while (curr != null ) {
nodes.add (curr);
curr = curr.next ;
}
// Fisher-Yates shuffle
Random rand = new Random();
int n = nodes.size ();
for (int i = n - 1; i > 0; i-- ) {
int j = rand.nextInt (i + 1);
Collections.swap (nodes, i, j);
}
// Reconstruct linked list
for (int i = 0; i < n - 1; i++ ) {
nodes.get (i).next = nodes.get (i + 1);
}
nodes.get (n - 1).next = null ;
return nodes.get (0);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class ListNode :
def __init__ (self, val: int = 0 , next: 'ListNode' = None ):
self. val = val
self. next = next
class Solution :
def shuffle_list (self, head: ListNode) -> ListNode:
if not head or not head. next:
return head
# Convert to list
nodes = []
curr = head
while curr:
nodes. append(curr)
curr = curr. next
# Fisher-Yates shuffle
n = len(nodes)
for i in range(n - 1 , 0 , - 1 ):
j = random. randint(0 , i)
nodes[i], nodes[j] = nodes[j], nodes[i]
# Reconstruct linked list
for i in range(n - 1 ):
nodes[i]. next = nodes[i + 1 ]
nodes[n - 1 ]. next = None
return nodes[0 ]
Complexity#
⏰ Time complexity: O(N)
, where N is the number of nodes. Single pass to collect nodes, O(N) for shuffling, O(N) for reconstruction
🧺 Space complexity: O(N)
, for storing all node references in the array
Method 2 - Reservoir Sampling with In-Place Reconstruction#
Intuition#
To prioritize space over time, we can use a modified reservoir sampling approach. We make multiple passes through the linked list: first to count nodes, then use reservoir sampling technique to build the shuffled list one position at a time. This reduces space complexity at the cost of increased time complexity.
Approach#
First pass: count the total number of nodes (n)
For each position i from 0 to n-1 in the result:
Use reservoir sampling to select the (i+1)th node for position i
Traverse the remaining list and select with probability 1/(remaining_nodes)
Remove the selected node from the original list
Add it to the result list
Handle edge cases for empty or single-node lists
Maintain pointers to efficiently remove nodes from the original list
Code#
Cpp
Go
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
private :
int countNodes(ListNode* head) {
int count = 0 ;
while (head) {
count++ ;
head = head-> next;
}
return count;
}
ListNode* removeNode (ListNode*& head, int index) {
if (index == 0 ) {
ListNode* node = head;
head = head-> next;
return node;
}
ListNode* prev = head;
for (int i = 0 ; i < index - 1 ; i++ ) {
prev = prev-> next;
}
ListNode* node = prev-> next;
prev-> next = node-> next;
return node;
}
public :
ListNode* shuffleListSpaceOptimized(ListNode* head) {
if (! head || ! head-> next) return head;
int n = countNodes(head);
ListNode* result = nullptr ;
ListNode* resultTail = nullptr ;
for (int i = 0 ; i < n; i++ ) {
int remaining = n - i;
int selectedIndex = rand() % remaining;
ListNode* selectedNode = removeNode(head, selectedIndex);
selectedNode-> next = nullptr ;
if (! result) {
result = resultTail = selectedNode;
} else {
resultTail-> next = selectedNode;
resultTail = selectedNode;
}
}
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func countNodes (head * ListNode ) int {
count := 0
for head != nil {
count ++
head = head .Next
}
return count
}
func removeNode (head ** ListNode , index int ) * ListNode {
if index == 0 {
node := * head
* head = (* head ).Next
return node
}
prev := * head
for i := 0 ; i < index - 1 ; i ++ {
prev = prev .Next
}
node := prev .Next
prev .Next = node .Next
return node
}
func shuffleListSpaceOptimized (head * ListNode ) * ListNode {
if head == nil || head .Next == nil {
return head
}
n := countNodes (head )
var result , resultTail * ListNode
for i := 0 ; i < n ; i ++ {
remaining := n - i
selectedIndex := rand .Intn (remaining )
selectedNode := removeNode (& head , selectedIndex )
selectedNode .Next = nil
if result == nil {
result = selectedNode
resultTail = selectedNode
} else {
resultTail .Next = selectedNode
resultTail = selectedNode
}
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
private int countNodes (ListNode head) {
int count = 0;
while (head != null ) {
count++ ;
head = head.next ;
}
return count;
}
private ListNode removeNode (ListNode[] headRef, int index) {
if (index == 0) {
ListNode node = headRef[ 0] ;
headRef[ 0] = headRef[ 0] .next ;
return node;
}
ListNode prev = headRef[ 0] ;
for (int i = 0; i < index - 1; i++ ) {
prev = prev.next ;
}
ListNode node = prev.next ;
prev.next = node.next ;
return node;
}
public ListNode shuffleListSpaceOptimized (ListNode head) {
if (head == null || head.next == null ) return head;
int n = countNodes(head);
ListNode[] headRef = {head};
ListNode result = null ;
ListNode resultTail = null ;
Random rand = new Random();
for (int i = 0; i < n; i++ ) {
int remaining = n - i;
int selectedIndex = rand.nextInt (remaining);
ListNode selectedNode = removeNode(headRef, selectedIndex);
selectedNode.next = null ;
if (result == null ) {
result = resultTail = selectedNode;
} else {
resultTail.next = selectedNode;
resultTail = selectedNode;
}
}
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution :
def count_nodes (self, head: ListNode) -> int:
count = 0
while head:
count += 1
head = head. next
return count
def remove_node (self, head_ref: List[ListNode], index: int) -> ListNode:
if index == 0 :
node = head_ref[0 ]
head_ref[0 ] = head_ref[0 ]. next
return node
prev = head_ref[0 ]
for i in range(index - 1 ):
prev = prev. next
node = prev. next
prev. next = node. next
return node
def shuffle_list_space_optimized (self, head: ListNode) -> ListNode:
if not head or not head. next:
return head
n = self. count_nodes(head)
head_ref = [head]
result = None
result_tail = None
for i in range(n):
remaining = n - i
selected_index = random. randint(0 , remaining - 1 )
selected_node = self. remove_node(head_ref, selected_index)
selected_node. next = None
if not result:
result = result_tail = selected_node
else :
result_tail. next = selected_node
result_tail = selected_node
return result
Complexity#
⏰ Time complexity: O(N²)
, where N is the number of nodes. For each of N positions, we traverse up to N nodes to select and remove
🧺 Space complexity: O(1)
, constant extra space as we modify the original list structure
Method 3 - Random Position Swapping with Limited Space#
Intuition#
A compromise between time and space is to perform multiple random swaps while traversing the list. We use a technique similar to bubble sort but with random selections. This doesn’t guarantee perfect uniform distribution but provides good practical randomness with limited space usage.
Approach#
Count the total number of nodes in the first pass
Perform multiple passes (e.g., 2*N passes) through the list
In each pass, select two random positions and swap their values
Use a single pass to perform each swap operation
The number of swaps ensures good mixing while maintaining O(1) space
Return the modified list
Code#
Cpp
Go
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
private :
ListNode* getNodeAt(ListNode* head, int index) {
for (int i = 0 ; i < index && head; i++ ) {
head = head-> next;
}
return head;
}
public :
ListNode* shuffleListRandomSwaps(ListNode* head) {
if (! head || ! head-> next) return head;
int n = countNodes(head);
// Perform multiple random swaps
for (int i = 0 ; i < 2 * n; i++ ) {
int pos1 = rand() % n;
int pos2 = rand() % n;
if (pos1 != pos2) {
ListNode* node1 = getNodeAt(head, pos1);
ListNode* node2 = getNodeAt(head, pos2);
swap(node1-> val, node2-> val);
}
}
return head;
}
private :
int countNodes(ListNode* head) {
int count = 0 ;
while (head) {
count++ ;
head = head-> next;
}
return count;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func getNodeAt (head * ListNode , index int ) * ListNode {
for i := 0 ; i < index && head != nil ; i ++ {
head = head .Next
}
return head
}
func shuffleListRandomSwaps (head * ListNode ) * ListNode {
if head == nil || head .Next == nil {
return head
}
n := countNodes (head )
// Perform multiple random swaps
for i := 0 ; i < 2 * n ; i ++ {
pos1 := rand .Intn (n )
pos2 := rand .Intn (n )
if pos1 != pos2 {
node1 := getNodeAt (head , pos1 )
node2 := getNodeAt (head , pos2 )
node1 .Val , node2 .Val = node2 .Val , node1 .Val
}
}
return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
private ListNode getNodeAt (ListNode head, int index) {
for (int i = 0; i < index && head != null ; i++ ) {
head = head.next ;
}
return head;
}
public ListNode shuffleListRandomSwaps (ListNode head) {
if (head == null || head.next == null ) return head;
int n = countNodes(head);
Random rand = new Random();
// Perform multiple random swaps
for (int i = 0; i < 2 * n; i++ ) {
int pos1 = rand.nextInt (n);
int pos2 = rand.nextInt (n);
if (pos1 != pos2) {
ListNode node1 = getNodeAt(head, pos1);
ListNode node2 = getNodeAt(head, pos2);
int temp = node1.val ;
node1.val = node2.val ;
node2.val = temp;
}
}
return head;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution :
def get_node_at (self, head: ListNode, index: int) -> ListNode:
for i in range(index):
if head:
head = head. next
return head
def shuffle_list_random_swaps (self, head: ListNode) -> ListNode:
if not head or not head. next:
return head
n = self. count_nodes(head)
# Perform multiple random swaps
for i in range(2 * n):
pos1 = random. randint(0 , n - 1 )
pos2 = random. randint(0 , n - 1 )
if pos1 != pos2:
node1 = self. get_node_at(head, pos1)
node2 = self. get_node_at(head, pos2)
node1. val, node2. val = node2. val, node1. val
return head
Complexity#
⏰ Time complexity: O(N²)
, where N is the number of nodes. We perform O(N) swaps, each requiring O(N) time to locate nodes
🧺 Space complexity: O(1)
, constant extra space as we only swap values in place
Notes#
Method 1 provides perfect uniform distribution but requires O(N) extra space
Method 2 prioritizes space (O(1)) over time, suitable when memory is extremely limited
Method 3 offers a practical compromise with good randomness and constant space
The choice between methods depends on the specific constraints of space vs. time
For cryptographic applications, Method 1 with Fisher-Yates is recommended for perfect uniformity
Method 2 and 3 are more suitable for general applications where perfect uniformity isn’t critical
All methods preserve the original node objects, only changing their arrangement or values
Consider using a proper random number generator for production applications
The problem demonstrates the classic trade-off between time and space complexity in algorithm design