Skip to main content

Reorder List

Problem Description​

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.

Examples​

Example 1: image

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

Example 2: image

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

Constraints​

  • The number of nodes in the list is in the range ([1,5∗104])([1, 5 * 10^4]).
  • 1 <= Node.val <= 1000

Solution for Reorder List​

Intuition​

Find the Middle:​

  • Use two pointers to traverse the list at different speeds (one moving one step at a time, the other two steps). When the faster pointer reaches the end, the slower pointer will be at the middle. This splits the list into two halves.

Reverse the Second Half:​

  • Reverse the second half of the list. This means changing the direction of the links between nodes in this part of the list so that the last node becomes the first node of this half.

Merge the Two Halves:​

  • Start from the beginning of the list and the beginning of the reversed second half.
  • Alternate nodes from each half to weave them together into a single reordered list.
  • Continue this process until all nodes are merged.

Implementation​

Live Editor
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}
// Function to reverse the linked list
function reverse(head) {
    let curr = head;
    let prev = null;
    let ptr = null;

    while (curr !== null) {
        ptr = curr.next;
        curr.next = prev;
        prev = curr;
        curr = ptr;
    }
    return prev;
}

// Function to reorder the linked list
function reorderList(head) {
    if (!head || !head.next) return;

    // Find the middle of the linked list
    let slow = head;
    let fast = head;
    let last = head;

    while (fast !== null && fast.next !== null) {
        last = slow;
        slow = slow.next;
        fast = fast.next.next;
    }

    // Split the list into two halves
    last.next = null;

    // Reverse the second half of the list
    let second = reverse(slow);
    let first = head;

    // Merge the two halves
    while (second) {
        let temp1 = first.next;
        let temp2 = second.next;

        first.next = second;
        second.next = temp1;

        first = temp1;
        second = temp2;
    }
}

const input = [1, 2, 3, 4, 5];

// Construct the linked list from the input array
let head = new Node(input[0]);
let current = head;
let stack = [head];
for (let i = 1; i < input.length; i++) {
    if (input[i] === null) continue;
    let newNode = new Node(input[i]);
    current.next = newNode;
    newNode.prev = current;
    current = newNode;
    if (input[i] !== null) {
        stack.push(current);
    }
}

// Flatten the linked list
let output = reorderList(head);

return (
    <div>
        <p>
            <b>Input: </b>{JSON.stringify(input)}
        </p>
        <p>
            <b>Output:</b> {output ? output.toString() : 'null'}
        </p>
    </div>
);
Result
Loading...

Code in Different Languages​

Written by @hiteshgahanolia
function createNode(val, next = null) {
 return { val, next };
}

function reverse(head) {
 let curr = head;
 let prev = null;
 let ptr = null;

 while (curr !== null) {
     ptr = curr.next;
     curr.next = prev;
     prev = curr;
     curr = ptr;
 }

 return prev;
}

function findMiddle(head) {
 let slow = head;
 let fast = head;

 while (fast !== null && fast.next !== null) {
     slow = slow.next;
     fast = fast.next.next;
 }

 return slow;
}

function reorderList(head) {
 let middle = findMiddle(head);
 let second = reverse(middle);
 let first = head;

 while (second !== null && first !== null) {
     let temp1 = first.next;
     let temp2 = second.next;

     if (first.next !== null) {
         first.next = second;
     }
     if (second.next !== null) {
         second.next = temp1;
     }

     second = temp2;
     first = temp1;
 }
}

// Example usage:
// Create a linked list
let head = createNode(1);
head.next = createNode(2);
head.next.next = createNode(3);
head.next.next.next = createNode(4);
head.next.next.next.next = createNode(5);

reorderList(head);

// Print the reordered list
let current = head;
while (current !== null) {
 console.log(current.val);
 current = current.next;
}

Complexity Analysis​

  • Time Complexity: O(N) O(N)
  • Space Complexity: O(1) O(1)

References​