problemhardalgorithmsdaily-coding-problem-337daily coding problem 337dailycodingproblem337

Uniformly Shuffle Linked List Nodes

HardUpdated: Aug 10, 2025

Problem

Given a linked list, uniformly shuffle the nodes. What if we want to prioritize space over time?

Examples

Example 1

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

Input: 5 -> NULL
Output: 5 -> NULL
Explanation:
Single node list remains unchanged as there's only one possible arrangement.

Example 3

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

Input: NULL
Output: NULL
Explanation:
Empty list remains empty after shuffling.

Example 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

  1. Traverse the linked list and store all node references in an array
  2. 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
  3. Reconstruct the linked list using the shuffled array order
  4. Update next pointers to reflect the new arrangement
  5. Return the new head of the shuffled list

Code

C++
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];
    }
};
Go
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]
}
Java
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);
    }
}
Python
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

  1. First pass: count the total number of nodes (n)
  2. 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
  3. Handle edge cases for empty or single-node lists
  4. Maintain pointers to efficiently remove nodes from the original list

Code

C++
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;
    }
};
Go
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
}
Java
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;
    }
}
Python
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

  1. Count the total number of nodes in the first pass
  2. Perform multiple passes (e.g., 2*N passes) through the list
  3. In each pass, select two random positions and swap their values
  4. Use a single pass to perform each swap operation
  5. The number of swaps ensures good mixing while maintaining O(1) space
  6. Return the modified list

Code

C++
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;
    }
};
Go
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
}
Java
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;
    }
}
Python
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

Comments