Reorder List

Reorder a linked list by interleaving nodes from the beginning and end

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Input/Output Specifications

Input: Head of a singly linked list
Output: Head of the reordered linked list
Constraints:
- The number of nodes in the list is in the range [1, 5 * 10^4]
- 1 <= Node.val <= 1000

Examples

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Solutions

Approach 1: Three Steps (Find Middle, Reverse, Merge)

This approach breaks the problem into three steps: find the middle, reverse the second half, and merge the two halves.

Algorithm:

Find the middle of the list using slow and fast pointers
Reverse the second half of the list
Merge the first half and reversed second half by interleaving nodes
Return the head of the reordered list

Python:

def reorderList(head):
    """
    Reorder linked list by interleaving nodes from beginning and end
    Time: O(n)
    Space: O(1)
    """
    if not head or not head.next:
        return head
    
    # Step 1: Find the middle of the list
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Step 2: Reverse the second half
    second_half = reverseList(slow.next)
    slow.next = None  # Split the list
    
    # Step 3: Merge the two halves
    first_half = head
    while second_half:
        # Store next nodes
        temp1 = first_half.next
        temp2 = second_half.next
        
        # Connect nodes
        first_half.next = second_half
        second_half.next = temp1
        
        # Move pointers
        first_half = temp1
        second_half = temp2
    
    return head

def reverseList(head):
    """Helper function to reverse a linked list"""
    prev = None
    current = head
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    return prev

Java:

class Solution {
    /**
     * Reorder linked list by interleaving nodes from beginning and end
     * Time: O(n)
     * Space: O(1)
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        
        // Step 1: Find the middle of the list
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Step 2: Reverse the second half
        ListNode secondHalf = reverseList(slow.next);
        slow.next = null; // Split the list
        
        // Step 3: Merge the two halves
        ListNode firstHalf = head;
        while (secondHalf != null) {
            // Store next nodes
            ListNode temp1 = firstHalf.next;
            ListNode temp2 = secondHalf.next;
            
            // Connect nodes
            firstHalf.next = secondHalf;
            secondHalf.next = temp1;
            
            // Move pointers
            firstHalf = temp1;
            secondHalf = temp2;
        }
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }
}

Go:

// reorderList - Reorder linked list by interleaving nodes from beginning and end
// Time: O(n)
// Space: O(1)
func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    
    // Step 1: Find the middle of the list
    slow := head
    fast := head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    // Step 2: Reverse the second half
    secondHalf := reverseList(slow.Next)
    slow.Next = nil // Split the list
    
    // Step 3: Merge the two halves
    firstHalf := head
    for secondHalf != nil {
        // Store next nodes
        temp1 := firstHalf.Next
        temp2 := secondHalf.Next
        
        // Connect nodes
        firstHalf.Next = secondHalf
        secondHalf.Next = temp1
        
        // Move pointers
        firstHalf = temp1
        secondHalf = temp2
    }
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head
    for current != nil {
        nextTemp := current.Next
        current.Next = prev
        prev = current
        current = nextTemp
    }
    return prev
}

JavaScript:

/**
 * Reorder linked list by interleaving nodes from beginning and end
 * Time: O(n)
 * Space: O(1)
 */
function reorderList(head) {
    if (head === null || head.next === null) {
        return;
    }
    
    // Step 1: Find the middle of the list
    let slow = head;
    let fast = head;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Step 2: Reverse the second half
    const secondHalf = reverseList(slow.next);
    slow.next = null; // Split the list
    
    // Step 3: Merge the two halves
    let firstHalf = head;
    let current = secondHalf;
    while (current !== null) {
        // Store next nodes
        const temp1 = firstHalf.next;
        const temp2 = current.next;
        
        // Connect nodes
        firstHalf.next = current;
        current.next = temp1;
        
        // Move pointers
        firstHalf = temp1;
        current = temp2;
    }
}

function reverseList(head) {
    let prev = null;
    let current = head;
    while (current !== null) {
        const nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

C#:

public class Solution {
    /// <summary>
    /// Reorder linked list by interleaving nodes from beginning and end
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        
        // Step 1: Find the middle of the list
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Step 2: Reverse the second half
        ListNode secondHalf = ReverseList(slow.next);
        slow.next = null; // Split the list
        
        // Step 3: Merge the two halves
        ListNode firstHalf = head;
        while (secondHalf != null) {
            // Store next nodes
            ListNode temp1 = firstHalf.next;
            ListNode temp2 = secondHalf.next;
            
            // Connect nodes
            firstHalf.next = secondHalf;
            secondHalf.next = temp1;
            
            // Move pointers
            firstHalf = temp1;
            secondHalf = temp2;
        }
    }
    
    private ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }
}

Approach 2: Using Stack

This approach uses a stack to store the second half of the list, then interleaves nodes.

Algorithm:

Find the middle of the list
Push the second half onto a stack
Interleave nodes from the first half and stack
Return the reordered list

Python:

def reorderListStack(head):
    """
    Reorder linked list using stack
    Time: O(n)
    Space: O(n)
    """
    if not head or not head.next:
        return head
    
    # Find the middle of the list
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Push second half onto stack
    stack = []
    current = slow.next
    slow.next = None  # Split the list
    
    while current:
        stack.append(current)
        current = current.next
    
    # Interleave nodes
    current = head
    while stack:
        node = stack.pop()
        temp = current.next
        current.next = node
        node.next = temp
        current = temp
    
    return head

Java:

class Solution {
    /**
     * Reorder linked list using stack
     * Time: O(n)
     * Space: O(n)
     */
    public void reorderListStack(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        
        // Find the middle of the list
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Push second half onto stack
        Stack<ListNode> stack = new Stack<>();
        ListNode current = slow.next;
        slow.next = null; // Split the list
        
        while (current != null) {
            stack.push(current);
            current = current.next;
        }
        
        // Interleave nodes
        current = head;
        while (!stack.isEmpty()) {
            ListNode node = stack.pop();
            ListNode temp = current.next;
            current.next = node;
            node.next = temp;
            current = temp;
        }
    }
}

Go:

// reorderListStack - Reorder linked list using stack
// Time: O(n)
// Space: O(n)
func reorderListStack(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    
    // Find the middle of the list
    slow := head
    fast := head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    // Push second half onto stack
    stack := make([]*ListNode, 0)
    current := slow.Next
    slow.Next = nil // Split the list
    
    for current != nil {
        stack = append(stack, current)
        current = current.Next
    }
    
    // Interleave nodes
    current = head
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        temp := current.Next
        current.Next = node
        node.Next = temp
        current = temp
    }
}

JavaScript:

/**
 * Reorder linked list using stack
 * Time: O(n)
 * Space: O(n)
 */
function reorderListStack(head) {
    if (head === null || head.next === null) {
        return;
    }
    
    // Find the middle of the list
    let slow = head;
    let fast = head;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Push second half onto stack
    const stack = [];
    let current = slow.next;
    slow.next = null; // Split the list
    
    while (current !== null) {
        stack.push(current);
        current = current.next;
    }
    
    // Interleave nodes
    current = head;
    while (stack.length > 0) {
        const node = stack.pop();
        const temp = current.next;
        current.next = node;
        node.next = temp;
        current = temp;
    }
}

C#:

public class Solution {
    /// <summary>
    /// Reorder linked list using stack
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public void ReorderListStack(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        
        // Find the middle of the list
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Push second half onto stack
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode current = slow.next;
        slow.next = null; // Split the list
        
        while (current != null) {
            stack.Push(current);
            current = current.next;
        }
        
        // Interleave nodes
        current = head;
        while (stack.Count > 0) {
            ListNode node = stack.Pop();
            ListNode temp = current.next;
            current.next = node;
            node.next = temp;
            current = temp;
        }
    }
}

Key Insights

Three-step approach: Find middle, reverse second half, merge
Interleaving pattern: Alternate between first half and reversed second half
Space optimization: O(1) space approach is preferred over O(n) stack approach
Pointer management: Careful handling of next pointers during merging
Edge case handling: Handle lists with 1 or 2 nodes properly

Edge Cases

Single node list
Two node list
Three node list
Even number of nodes
Odd number of nodes

Test Cases

# Test case 1: Even number of nodes
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
# reorderList(head1) -> [1,4,2,3]

# Test case 2: Odd number of nodes
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
head2.next.next.next = ListNode(4)
head2.next.next.next.next = ListNode(5)
# reorderList(head2) -> [1,5,2,4,3]

# Test case 3: Two nodes
head3 = ListNode(1)
head3.next = ListNode(2)
# reorderList(head3) -> [1,2]

# Test case 4: Single node
head4 = ListNode(1)
# reorderList(head4) -> [1]

Follow-up Questions

How would you handle very large lists?
Can you solve this with O(1) space?
How would you handle lists with cycles?
What if you need to preserve the original list?

Common Mistakes

Not properly splitting the list at the middle
Incorrect pointer management during merging
Not handling edge cases like single or two nodes
Forgetting to set the next pointer of the last node
Off-by-one errors in middle finding
Memory leaks when not properly managing pointers