Interleaved Reversal of Nodes in a Sequence — Problem Statement & Solution Guide

Linked ListHardReverse Linked List

TimeO(n)

SpaceO(1)

Problem Description

Given a sequence of interconnected nodes, rearrange the nodes such that the sequence alternates between nodes from the first half and nodes from the second half of the original sequence, effectively creating an interleaved reversal.

DSA Pattern Breakdown

"Interleaved Reversal of Nodes in a Sequence"

hard

WHY DOES IT MATTER?

Interleaved reversal exemplifies the "two‑pointer + in‑place reversal" pattern, a cornerstone for many real‑world list manipulations such as reordering messages, load‑balancing streams, and implementing palindrome checks without extra memory. Mastery of this pattern demonstrates a candidate’s ability to write cache‑friendly, low‑overhead code—critical for performance‑sensitive systems.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that reversing the second half transforms a backward‑looking problem into a forward‑only traversal, allowing a single pass merge. This eliminates the need for auxiliary arrays or stacks, collapsing both time and space complexity to their theoretical minima.

REAL-WORLD CONNECTION

Think of a conveyor belt delivering packages from two warehouses: one supplies items in original order, the other supplies items in reverse order. Merging them alternately ensures balanced loading, similar to how distributed log aggregators interleave forward and backward event streams to maintain temporal consistency.

During an interview, first sketch the three‑step pipeline on the whiteboard, then write the reversal routine as a separate helper. Keep a temporary pointer for the next node before re‑linking to avoid losing access—this tiny detail often trips candidates.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The interleaved reversal problem is a classic linked‑list transformation that requires reordering nodes so that the final sequence alternates between the original first half and the reversed second half (e.g., L0 → Ln → L1 → Ln‑1 → …). The naive solution copies all nodes into an auxiliary array, then rebuilds the list by picking elements from the front and back. While conceptually simple, this approach incurs O(n) extra space and suffers from cache‑miss penalties on very large inputs, making it unsuitable for memory‑constrained environments such as embedded systems or high‑throughput services. Moreover, the extra allocation step can dominate runtime when the list contains millions of nodes, violating the strict latency SLAs common in fintech and real‑time analytics pipelines.

The optimal paradigm leverages three in‑place operations: (1) locate the midpoint using the fast‑slow pointer technique, (2) reverse the second half of the list in O(n) time with O(1) auxiliary space, and (3) merge the two halves by alternating pointers. This three‑step pipeline respects the linked‑list’s sequential access pattern, avoids any additional memory allocation, and runs in linear time. The reversal step is the key insight: by flipping the direction of the second half, we can interleave nodes without back‑tracking, which is impossible in a singly linked list without extra storage. The overall algorithm thus satisfies the optimal time‑space bound for this class of problems.

Interview Questions on This Problem

Q1How would you reorder a singly linked list to achieve the pattern L0 → Ln → L1 → Ln‑1 → … in O(n) time and O(1) space?

First, use a fast and slow pointer to find the middle of the list. Then reverse the second half in place. Finally, merge the two halves by alternately linking nodes from the first and reversed second half, taking care to update next pointers correctly.

Q2What modifications are needed to handle lists with an odd number of nodes while performing the interleaved reversal?

When the list length is odd, the middle node belongs to the first half. After finding the midpoint, ensure the first half ends at the middle node and the second half starts at middle.next. During the merge, the extra middle node will naturally remain at the end of the reordered list.

Q3Can you restore the original list order after performing the interleaved reversal without using extra memory? If so, how?

Yes. After the interleaved list is built, split it back into two halves by traversing to the node where the original first half ends, reverse the second half again to restore its original direction, and then concatenate the halves. This uses the same in‑place reversal technique and maintains O(1) extra space.

Examples

Example 1

Input

1 -> 2 -> 3 -> 4 -> 5 -> 6

Output

1 -> 6 -> 2 -> 5 -> 3 -> 4

Explanation: Step-by-step: 1. Split the linked list into two halves: 1 -> 2 -> 3 and 4 -> 5 -> 6. 2. Reverse the second half: 6 -> 5 -> 4. 3. Interleave the two halves: 1 -> 6 -> 2 -> 5 -> 3 -> 4

Example 2

Input

7 -> 8 -> 9

Output

7 -> 9 -> 8

Explanation: Step-by-step: 1. Split the linked list into two halves: 7 -> 8 and 9. 2. Reverse the second half: 9. 3. Interleave the two halves: 7 -> 9 -> 8

Constraints

The sequence can contain any number of nodes.
The reversal should be done in-place, without using any additional data structures.
The time complexity should be O(n), where n is the number of nodes in the sequence.
The space complexity should be O(1), as only a constant amount of space can be used.

Optimal Approach & Strategy

Locate the midpoint, reverse the second half in place, and merge the two halves by alternating nodes.

Brute Force Approach

Copy all node values into an array, then rebuild the list by alternately taking elements from the start and end of the array.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(head) {
    if (!head || !head.next || !head.next.next) return head;
    let slow = head, fast = head, second = head.next, firstEnd = null, secondEnd = null;
    while (fast.next && fast.next.next) {
      slow = slow.next;
      fast = fast.next.next;
    }
    firstEnd = slow.next;
    secondEnd = firstEnd;
    while (secondEnd.next) {
      secondEnd = secondEnd.next;
    }
    secondEnd.next = null;
    second = reverseList(second);
    let result = head;
    while (firstEnd) {
      result = mergeTwoLists(result, firstEnd);
      result = mergeTwoLists(result, second);
      firstEnd = firstEnd.next;
      second = second.next;
    }
    return result;
  }

class Solution {
public:
    ListNode* solution(ListNode* head) {
      if (!head || !head->next || !head->next->next) return head;
      ListNode* slow = head;
      ListNode* fast = head;
      ListNode* second = head->next;
      ListNode* firstEnd = nullptr;
      ListNode* secondEnd = nullptr;
      while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
      }
      firstEnd = slow->next;
      secondEnd = firstEnd;
      while (secondEnd->next) {
        secondEnd = secondEnd->next;
      }
      secondEnd->next = nullptr;
      second = reverseList(second);
      ListNode* result = head;
      while (firstEnd) {
        result = mergeTwoLists(result, firstEnd);
        result = mergeTwoLists(result, second);
        firstEnd = firstEnd->next;
        second = second->next;
      }
      return result;
    }
  };

class Solution {
    public ListNode solution(ListNode head) {
      if (!head || !head.next || !head.next.next) return head;
      ListNode slow = head, fast = head, second = head.next, firstEnd = null, secondEnd = null;
      while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
      }
      firstEnd = slow.next;
      secondEnd = firstEnd;
      while (secondEnd.next) {
        secondEnd = secondEnd.next;
      }
      secondEnd.next = null;
      second = reverseList(second);
      ListNode result = head;
      while (firstEnd) {
        result = mergeTwoLists(result, firstEnd);
        result = mergeTwoLists(result, second);
        firstEnd = firstEnd.next;
        second = second.next;
      }
      return result;
    }
  }

def solution(head):
    if not head or not head.next or not head.next.next:
      return head
    slow = head
    fast = head
    second = head.next
    first_end = None
    second_end = None
    while fast.next and fast.next.next:
      slow = slow.next
      fast = fast.next.next
    first_end = slow.next
    second_end = first_end
    while second_end.next:
      second_end = second_end.next
    second_end.next = None
    second = reverseList(second)
    result = head
    while first_end:
      result = mergeTwoLists(result, first_end)
      result = mergeTwoLists(result, second)
      first_end = first_end.next
      second = second.next
    return result

function solution(head) {
    if (!head || !head.next || !head.next.next) return head;
    let slow = head, fast = head, second = head.next, firstEnd = null, secondEnd = null;
    while (fast.next && fast.next.next) {
      slow = slow.next;
      fast = fast.next.next;
    }
    firstEnd = slow.next;
    secondEnd = firstEnd;
    while (secondEnd.next) {
      secondEnd = secondEnd.next;
    }
    secondEnd.next = null;
    second = reverseList(second);
    let result = head;
    while (firstEnd) {
      result = mergeTwoLists(result, firstEnd);
      result = mergeTwoLists(result, second);
      firstEnd = firstEnd.next;
      second = second.next;
    }
    return result;
  }

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Interleaved Reversal of Nodes in a Sequence Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Linked List

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Interleaved Reversal of Nodes in a Sequence — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor