Reorder Linked List - Rotate and Rearrange Algorithm

The linked list rotation problem involves rearranging nodes in a linked list according to specific patterns, commonly requiring manipulation of node connections to achieve desired ordering while maintaining optimal performance characteristics.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected input size and are there any constraints on it?
2. Are duplicates allowed in the linked list?
3. Should I return a new list or modify the original list in-place?
4. Can I mutate the input structure, or should I preserve it?
5. What is the target time complexity for the follow-up?

Restate the pattern or problem type in your own words: The reorder/rotate linked list pattern involves rearranging the nodes of a singly linked list according to a specific rotation or reordering scheme. This typically means taking the last k nodes of the list and moving them to the front, or rotating the list by a certain number of positions.

Clarify the signal words and constraint shape that point to it: Signal words include "rotate," "reorder," "move last k nodes to front," "shift," or "rearrange." The constraint shape often involves a fixed rotation count k, where k is typically less than or equal to the list length, and operations that need to be done in linear time.

Note any assumptions you are making: I'm assuming the input is a valid singly linked list with at least one node, and that k is a non-negative integer. I'm also assuming that the list can be modified in-place.

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern is primarily suited for static scenarios where the entire list is available for processing. It's not typically used in streaming or online settings where elements arrive one at a time, as the rotation logic requires knowledge of the list's full structure and length.

The core insight is that we can find the rotation point efficiently by using two pointers or by calculating the effective rotation (k mod length) to avoid unnecessary full rotations.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Rotate" or "reorder" linked list elements
• "Move last k elements to front" or similar phrasing
• "Reorganize" or "restructure" the list in a specific way
• "K steps" or "k positions" mentioned as rotation distance
• "Circular" or "cyclic" behavior implied in the problem

Why this pattern fits better than the most common alternatives: This pattern is specifically designed for linked list rotation problems where we need to efficiently rearrange nodes in O(n) time and O(1) space. Unlike array rotation problems that can be solved with modular arithmetic, linked list rotation requires pointer manipulation and careful handling of node connections. The approach differs from general linked list reversal or merging problems because it maintains the structural integrity while shifting elements in a circular fashion.

Conditions where a variation or related pattern applies instead:

• If the problem asks for reversing sublists, use the "Reverse Linked List" pattern
• If we need to reorder nodes based on values (like odd-even partitioning), use "Partition Linked List"
• If the rotation is based on value comparisons rather than position-based shifting, use "Sort Linked List" pattern
• For circular linked list problems, consider "Detect Cycle in Linked List" pattern

The core insight that makes this pattern work: The key insight is recognizing that rotating a linked list by k positions means we're essentially splitting the list at position (n-k) and reconnecting the segments. By first calculating the length, we can determine the exact split point and perform the rotation in a single pass through the list. This approach leverages the fact that we can find any node in O(n) time and manipulate pointers to achieve the desired reordering without needing additional space for storing nodes.

3. Approach Evolution

Interview communication script:

My first instinct is to think about how I can reorder a linked list by rotating it, which sounds like I need to move nodes from the end to the beginning or vice versa. But let me think about this more carefully - if I'm rotating a list by k positions, that means I want to move the last k nodes to the front.

But wait, if k is larger than the list length, I need to handle that properly. Also, if k is 0 or a multiple of the list length, the list should remain unchanged.

Let me think about how to approach this efficiently. A brute force approach would be to find the tail, connect it to head to make a circular list, then break it at the right position. But that requires traversing the list multiple times.

Actually, I think there's a better way - I can find the node that will become the new tail (at position n-k-1 from the start), then break the list there and rewire the connections. But I need to be careful about edge cases like k being larger than n.

Let me think about the constraints more carefully. If I have a list of length n and rotate by k positions, I want to move the last k nodes to the front. But if k > n, I should take k mod n to avoid unnecessary full rotations.

I notice that if I maintain the invariant that I always work with k mod n, and find the exact break point, I can reduce this to O(n) time and O(1) space by using two pointers.

First, let me consider a brute force approach: I could traverse to find the length, then move nodes one by one from tail to head. But that's O(n²) because for each rotation, I need to traverse the list.

A better approach is to use two pointers - one fast pointer that moves k steps ahead, then both move together until the fast pointer reaches the end. This way I can find the break point in one pass.

The key insight is that if I want to rotate by k positions, the new head will be at position n-k (0-indexed), so I need to find that node and break the list there.

Brute-force approach and why it is not ideal:

The brute force approach would involve:

1. Finding the length of the list O(n)
2. For each rotation step, moving the last node to the front O(n)
3. Repeating k times

This results in O(n×k) time complexity, which is inefficient when k is large. Also, it requires multiple passes through the list and can be quite slow.

Improved approach and the key optimization:

The improved approach uses a two-pointer technique:

1. Find the length of the list O(n)
2. Normalize k to k mod n to handle cases where k > n
3. Use two pointers - one fast pointer that moves k steps ahead, then both move until fast reaches the end
4. The slow pointer will be at the break point

The key optimization is that instead of doing k individual rotations, I find where to make the cut in one pass through the list.

Final approach with step-by-step reasoning:

1. First, I need to handle edge cases - empty list or k=0 means no rotation needed
2. Find the length of the list by traversing once
3. Normalize k to avoid unnecessary full rotations: k = k % length
4. Use two pointers approach:
   • Move one pointer k steps ahead to create a gap of k nodes
   • Then move both pointers until the fast pointer reaches the end
   • The slow pointer will now be at the node before the new head
5. Break the list at that point and rewire connections

Important invariants that must hold:

• The new head will be at position (length - k) from the beginning
• The tail of the original list should connect to the original head
• The new tail should be at position (length - k - 1) from the beginning

This approach ensures we make exactly one pass through the list and only use constant extra space.

4. Data Structure Choice

For the reorder/rotate linked list problem, the primary data structure is a singly linked list with ListNode objects containing val and next fields.

Why Each Data Structure Is Needed

Singly Linked List:

• The problem explicitly operates on a linked list structure, so we must work with ListNode objects
• Each node needs to maintain a reference to the next node in the sequence
• The next pointer is essential for traversing and reordering the list

Additional Helper Structures:

• Two Pointers (Slow/Fast): Used to find the middle of the list in O(n) time
• Stack: Can be used as an alternative approach to store nodes for reordering (though not required for optimal solution)
• Temporary Variables: For swapping references during reordering operations

Time and Space Impact

Primary Data Structure (Linked List):

• Time: O(n) for traversal operations
• Space: O(1) additional space (excluding input list itself)

Two Pointers Approach:

• Time: O(n) for finding middle and reversing
• Space: O(1) - only using a constant number of pointers

Stack-Based Approach:

• Time: O(n) for stack operations
• Space: O(n) - storing all nodes in the stack

Helper Structures for Implementation

Dummy Node:

• Used to simplify edge case handling when modifying the head of the list
• Eliminates need for special handling of the first node in reordering operations

Reference Pointers:

• slow, fast, prev, current pointers for traversal and manipulation
• These are essential for the two-pointer technique to find the middle and reverse portions

The chosen approach uses only O(1) extra space beyond the input list, making it optimal for memory usage while maintaining O(n) time complexity. The solution avoids using additional data structures like stacks that would increase space complexity to O(n).

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works:

Example: 1 -> 2 -> 3 -> 4 -> 5 with k = 2

Step 1: Find the length and connect tail to head

• Length = 5, so we have 1 -> 2 -> 3 -> 4 -> 5 -> 1 (circular)
• Tail points to node 5, which now points to head node 1

Step 2: Calculate effective rotation

• k = 2, length = 5, so effective k = 2 % 5 = 2
• We need to break the list after 3 nodes (at position 3 from head)

Step 3: Find new tail and new head

• New tail is at position 3 (node 3)
• New head becomes node 4

Step 4: Break the circular list

• Set node3.next = null
• Return node4 as new head

Final result: 4 -> 5 -> 1 -> 2 -> 3

The algorithm handles edge cases properly:

• When k = 0 or k is multiple of length, no rotation occurs
• When k > length, we use modulo to get effective rotation
• For single node or empty list, no changes occur

The key insight is that we can make a circular list temporarily to easily find the break point, then restore the linear structure with proper connections.

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

6. Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // Handle edge cases
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        
        // Step 1: Find the length of the list and connect tail to head
        ListNode tail = head;
        int length = 1;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }
        
        // Optimize k to avoid unnecessary rotations
        k = k % length;
        if (k == 0) {
            return head; // No rotation needed
        }
        
        // Step 2: Make the list circular by connecting tail to head
        tail.next = head;
        
        // Step 3: Find the new tail (at position length - k - 1)
        ListNode newTail = head;
        for (int i = 0; i < length - k - 1; i++) {
            newTail = newTail.next;
        }
        
        // Step 4: New head is the node after newTail
        ListNode newHead = newTail.next;
        
        // Step 5: Break the circle to form the rotated list
        newTail.next = null;
        
        return newHead;
    }
}

This solution efficiently rotates a linked list by making it circular, finding the correct split point, and breaking the circle to form the rotated result. The approach avoids multiple passes by calculating the effective rotation count and using the circular property to locate the new head position.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the linked list to find the tail and count nodes, then another pass to find the split point and reconnect the list. Both passes are linear in the number of nodes, so the overall time complexity is O(n).

Space Complexity: O(1)

The solution uses only a constant amount of extra space for pointers and counters. No additional data structures are created that scale with input size, making it O(1) space complexity.

Why These Bounds Are Correct:

The linear time complexity comes from the fact that we visit each node exactly once in our two-pass approach. The first pass counts nodes and finds the tail, the second pass identifies where to split and reconnect. Since we're not using any recursive calls or nested loops, the runtime grows linearly with input size.

The constant space complexity is achieved because we only maintain a few pointer variables (head, tail, slow, fast) and integer counters that don't depend on input size. The algorithm modifies the list in-place without requiring additional storage structures.

Optimality:

This solution is optimal for the problem as stated. Since we must examine each node at least once to understand the list structure and perform the reordering, O(n) time complexity is unavoidable. The O(1) space usage is also optimal for an in-place reordering operation, as we cannot avoid using a constant amount of extra variables regardless of input size.

The solution achieves the best possible trade-off between time and space complexity for this constraint-based linked list reordering problem.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty list: Handle head == null case explicitly to avoid null pointer exceptions
• Single node: List with only one node should return the same list unchanged
• Two nodes: Need to verify rotation works correctly when k = 1 or k = 2

Duplicate Values and Repeated States

• Lists with duplicate values (e.g., 1->1->2->2) should work correctly without breaking the rotation logic
• When k is a multiple of list length, the result should be identical to original list
• The algorithm must handle cases where rotation count equals list size (no change needed)

Boundary Conditions

• k = 0: Should return original list unchanged
• k > length: Must handle modulo arithmetic correctly to avoid unnecessary rotations
• k = length: Should return the same list (full rotation)
• Large k values: Need to handle k % length properly to avoid overflow or incorrect results

Common Implementation Mistakes

• Incorrect pointer manipulation: Failing to properly disconnect and reconnect nodes can lead to cycles or lost references
• Off-by-one errors: Miscounting nodes during the rotation process, particularly when finding the split point
• Not updating head pointer: When rotating, the new head might change but isn't properly reassigned
• Missing null checks: Not checking for null next pointers when traversing the list
• Incorrect modulo calculation: Using k % length without considering that k might be larger than list size
• Failing to handle k = 0 case: Not recognizing that zero rotations should return the original list

Additional Considerations

• Integer overflow: When k is very large, ensure modulo operation handles it correctly
• Memory leaks: Ensure no dangling references remain after reordering operations
• Inconsistent behavior: The solution should behave consistently for both small and large rotation values

// Example edge case handling:
// Input: [1,2,3,4,5], k = 0 → Output: [1,2,3,4,5]
// Input: [1,2,3,4,5], k = 5 → Output: [1,2,3,4,5] 
// Input: [1,2,3,4,5], k = 7 → Output: [4,5,1,2,3] (k % 5 = 2)

9. Alternative Approaches

There are several alternative approaches to solving the linked list rotation problem, each with different trade-offs:

Approach 1: Two-Pass with Array Conversion

• Convert the linked list to an array, perform rotation on the array, then reconstruct the linked list
• Time: O(n), Space: O(n)
• Pros: Simple to implement, easy to understand
• Cons: Extra space overhead, requires two passes through the data

Approach 2: Naive Rotation by One

• For k rotations, perform k individual single-node rotations
• Time: O(n×k), Space: O(1)
• Pros: Simple logic, no extra space
• Cons: Inefficient for large k values, O(n×k) time complexity

Approach 3: Find Tail and Reconnect

• Find the tail node, connect it to head to make a circular list
• Then find the new tail at position (n-k)%n and break the circle
• Time: O(n), Space: O(1)
• Pros: Single pass, optimal space usage
• Cons: Slightly more complex to implement correctly

Approach 4: Stack-Based Reversal

• Use a stack to reverse segments of the list
• Time: O(n), Space: O(n) in worst case
• Pros: Leverages stack operations naturally
• Cons: Extra space overhead, more complex logic flow

The chosen solution using fast/slow pointers is preferred because it's the most intuitive, requires only one pass through the list, and achieves optimal O(1) space complexity while maintaining clean code structure. The stack-based approach is less intuitive and the naive rotation approach is inefficient for large k values.

The two-pass array conversion is most suitable when the problem constraints allow extra space usage and simplicity is preferred over optimal performance. The stack-based approach might be preferred in environments where stack operations are more familiar or when the problem naturally fits a stack-based pattern.

10. Test Cases

public class LinkedListRotationTestCases {
    
    // Test case 1: Basic rotation
    // Input: [1,2,3,4,5], k = 2
    // Expected: [4,5,1,2,3]
    public void testBasicRotation() {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        Solution solution = new Solution();
        ListNode result = solution.rotateRight(head, 2);
        
        // Verify rotation
        assert result.val == 4;
        assert result.next.val == 5;
        assert result.next.next.val == 1;
        assert result.next.next.next.val == 2;
        assert result.next.next.next.next.val == 3;
    }
    
    // Test case 2: k larger than list length
    // Input: [0,1,2], k = 4
    // Expected: [2,0,1] (equivalent to k=1)
    public void testLargeK() {
        ListNode head = new ListNode(0);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        
        Solution solution = new Solution();
        ListNode result = solution.rotateRight(head, 4);
        
        assert result.val == 2;
        assert result.next.val == 0;
        assert result.next.next.val == 1;
    }
    
    // Test case 3: Empty list
    // Input: [], k = 1
    // Expected: []
    public void testEmptyList() {
        Solution solution = new Solution();
        ListNode result = solution.rotateRight(null, 1);
        assert result == null;
    }
    
    // Test case 4: Single node
    // Input: [1], k = 1
    // Expected: [1]
    public void testSingleNode() {
        ListNode head = new ListNode(1);
        Solution solution = new Solution();
        ListNode result = solution.rotateRight(head, 1);
        
        assert result.val == 1;
        assert result.next == null;
    }
    
    // Test case 5: k = 0
    // Input: [1,2,3], k = 0
    // Expected: [1,2,3]
    public void testZeroRotation() {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        
        Solution solution = new Solution();
        ListNode result = solution.rotateRight(head, 0);
        
        assert result.val == 1;
        assert result.next.val == 2;
        assert result.next.next.val == 3;
    }
    
    // Test case 6: k equals list length
    // Input: [1,2,3], k = 3
    // Expected: [1,2,3] (no change)
    public void testKEqualsLength() {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        
        Solution solution = new Solution();
        ListNode result = solution.rotateRight(head, 3);
        
        assert result.val == 1;
        assert result.next.val == 2;
_assert result.next.next.val == 3;
    }
}

11. Final Summary

The core idea is to efficiently reorder a linked list by rotating it k positions to the right, which can be achieved by finding the split point and reassembling the list in O(n) time with O(1) space complexity. This solution works by leveraging the circular nature of a rotated list and using two pointers to find the correct break point, making it optimal for the given constraints where we must maintain the original node objects and avoid additional memory allocation. The key insight that makes it efficient is recognizing that rotation can be decomposed into a simple reconnection operation once we identify the proper split point.