Reorder List – LinkedIn Interview Question

Section 1: Introduction

In this lesson, we’re solving a common LinkedIn interview question: Reorder List.

This problem is frequently asked in software engineering interviews and tests your understanding of linked list manipulation, pointer logic, and in-place data structure changes.

Section 2: Problem Description

You are given the head of a singly linked list. The list is initially in the form:

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

You need to reorder it into the following pattern:

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

Important constraints:

• You may not modify the values of the list’s nodes.

• Only the pointers (links between nodes) can be changed.

Example 1:

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

Example 2:

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

Section 3: High-Level Idea

To reorder the list in the required format, we follow three main steps:

1. Find the middle of the linked list using the slow and fast pointer technique.

2. Reverse the second half of the list starting from the middle.

3. Merge the two halves — alternating nodes from each half.

Each step is done in O(n) time, and we use constant space — no extra memory is needed beyond a few pointers.

Section 4: Code Walkthrough (C++)

Here’s the full implementation:

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;

        // Step 1: Find the middle
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Step 2: Reverse the second half
        ListNode* prev = nullptr;
        ListNode* curr = slow->next;
        slow->next = nullptr;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Step 3: Merge two halves
        ListNode* first = head;
        ListNode* second = prev;
        while (second) {
            ListNode* temp1 = first->next;
            ListNode* temp2 = second->next;

            first->next = second;
            second->next = temp1;

            first = temp1;
            second = temp2;
        }
    }
};

Section 5: Step-by-Step Breakdown

Step 1: Find the Middle

We use the slow and fast pointer approach:

• slow moves one step at a time.

• fast moves two steps at a time.
  When fast reaches the end, slow is at the midpoint.

Step 2: Reverse the Second Half

We reverse the list starting from the node after the midpoint.
This gives us the second half in reverse order — which we’ll use to interleave with the first half.

Step 3: Merge the Halves

We now merge the two halves:

• Take a node from the first half.

• Take a node from the reversed second half.

• Alternate until the list is fully reordered.

Section 6: Summary

To summarize:

• We used the fast and slow pointer technique to find the midpoint.

• We reversed the second half of the list in-place.

• We merged the two halves node by node to form the required pattern.

This efficient solution runs in O(n) time, uses O(1) space, and solves a real interview problem from LinkedIn and other top tech companies.