Reorder List

We are given the head reference 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 → …

Example

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

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

Approach

Let us understand the solution with the help of the above example.

Step 1 : Find the midpoint of the linkedlist.

Here, the midpoint of the linkedlist is the node with the value 3.

Step 2 : Split the linkedlist from the midpoint.

Step 3 : Reverse the second list.

Step 4 : Connect both lists (A and B) such that  A0 -> B0 -> A1 -> B1 -> A2 -> B2 ….

Complexity

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

Code

# Java Code

import java.util.*;

class ReorderLinkedList {

    static class Node {
        int num;
        Node next;

        Node(int val) {
            num = val;
            next = null;
        }
    }

    private Node head = null;

    public void insertNode(int val) {
        if (head == null) {
            head = new Node(val);
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = new Node(val);
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.num);
            if (current.next != null) {
                System.out.print("->");
            }
            current = current.next;
        }
        System.out.println();
    }

    private Node findMiddle() {
        Node slow = head;
        Node fast = head;

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

        return slow;
    }

    private Node reverse(Node node) {
        Node curr = node;
        Node prev = null;

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

        return prev;
    }

    public void reorderList() {
        if (head == null || head.next == null) return;

        Node mid = findMiddle();
        Node secondHalf = reverse(mid.next);
        mid.next = null;

        Node firstHalf = head;

        while (firstHalf != null && secondHalf != null) {
            Node temp1 = firstHalf.next;
            Node temp2 = secondHalf.next;

            firstHalf.next = secondHalf;
            secondHalf.next = temp1;

            firstHalf = temp1;
            secondHalf = temp2;
        }
    }

    public static void main(String[] args) {
        ReorderLinkedList llm = new ReorderLinkedList();

        // Creation of lists
        llm.insertNode(1);
        llm.insertNode(2);
        llm.insertNode(3);
        llm.insertNode(4);
        llm.insertNode(5);

        // Printing of the list
        System.out.print("Input List: ");
        llm.printList();

        // Reordering list
        llm.reorderList();

        // Printing of the reordered list
        System.out.print("Reordered List: ");
        llm.printList();
    }
}

Output

Input List: 1->2->3->4->5
Reordered List: 1->5->2->4->3