The following shot discusses the standard problem of rearranging any given linked list with nodes ($0, 1, 2, 3 .... n-3, n-2, n-1, n$) into a linked list with alternate nodes ($0, n, 1, n-1, 2, n-2, 3, n-3$) and so on.

# Algorithm

The problem can be solved as efficient as O(n) using the following implementation.

1. Find the middle of linked list.
2. Separate the list into two halves and reverse the second half.
3. Rejoin both the lists in alternate order.

#include<bits/stdc++.h> 
using namespace std; 
   
struct Node 
{ 
    char data; 
    struct Node *next; 
}; 
  
Node* newNode(char key) 
{ 
    Node *temp = new Node; 
    temp->data = key; 
    temp->next = NULL; 
    return temp; 
} 
  
void reverselist(Node **head) 
{ 
    Node *prev = NULL, *curr = *head, *next; 
  
    while (curr) 
    { 
        next = curr->next; 
        curr->next = prev; 
        prev = curr; 
        curr = next; 
    } 
  
    *head = prev; 
} 
  
void printlist(Node *head) 
{ 
    cout<<"| ";
    while (head != NULL) 
    { 
        cout << head->data << " "; 
        if(head->next) cout << "| ---> | "; 
        head = head->next; 
    } 
    cout << "|" << endl; 
}

void reorder(Node **head) 
{ 
    //Locating the middle point  
    Node *p1 = *head, *p2 = p1->next; 
    while (p2 && p2->next) 
    { 
        p1 = p1->next; 
        p2 = p2->next->next; 
    } 
  
    //Spliting the linked list  
    Node *head1 = *head; 
    Node *head2 = p1->next; 
    p1->next = NULL; 
  
    //Reverse the second half
    reverselist(&head2); 
  
    //Merge alternate nodes 
    *head = newNode(0);  
    Node *curr = *head; 

    while (head1 != NULL || head2 != NULL) 
    { 
        if (head1 != NULL) 
        { 
            curr->next = head1; 
            curr = curr->next; 
            head1 = head1->next; 
        } 
  
        if (head2 != NULL) 
        { 
            curr->next = head2; 
            curr = curr->next; 
            head2 = head2->next; 
        } 
    } 

    *head = (*head)->next; 
} 

int main() 
{ 
    Node *head = newNode('A'); 
    head->next = newNode('B'); 
    head->next->next = newNode('C'); 
    head->next->next->next = newNode('D'); 
    head->next->next->next->next = newNode('E');
    head->next->next->next->next->next = newNode('F');
    head->next->next->next->next->next->next = newNode('G'); 
  
    printlist(head);
    reorder(&head);
    printlist(head);
} 

class LinkedList { 
  
    static Node head;  // head of the list 
  
  
    /* Node Class */
    static class Node { 
  
        char data; 
        Node next; 
  
        // Constructor to create a new node 
        Node(char d) { 
            data = d; 
            next = null; 
        } 
    } 
  
    void printlist(Node node) { 
        if (node == null) { 
            return; 
        } 
        System.out.print("| ");
        while (node != null) { 
            System.out.print(node.data); 
            if (node.next != null)
            {
                System.out.print(" | --> | ");
            }
            node = node.next; 
        } 
        System.out.print(" |");
    } 
  
    Node reverselist(Node node) { 
        Node prev = null, curr = node, next; 
        while (curr != null) { 
            next = curr.next; 
            curr.next = prev; 
            prev = curr; 
            curr = next; 
        } 
        node = prev; 
        return node; 
    } 

     void reorder(Node node) { 
  
        //Finding the middle point 
        Node p1 = node, p2 = p1.next; 
        while (p2 != null && p2.next != null) { 
            p1 = p1.next; 
            p2 = p2.next.next; 
        } 
  
        //Spliting the linked list 
        
        Node node1 = node; 
        Node node2 = p1.next; 
        p1.next = null; 
  
        //Reverse the second half
        node2 = reverselist(node2); 
  
        // 4) Merge alternate nodes 
        node = new Node('X'); 
        Node curr = node; 
        while (node1 != null || node2 != null) {   
            
            if (node1 != null) { 
                curr.next = node1; 
                curr = curr.next; 
                node1 = node1.next; 
            } 

            if (node2 != null) { 
                curr.next = node2; 
                curr = curr.next; 
                node2 = node2.next; 
            } 
        } 
        node = node.next; 
    } 

    public static void main(String[] args) { 
  
        LinkedList list = new LinkedList(); 
        list.head = new Node('A'); 
        list.head.next = new Node('B'); 
        list.head.next.next = new Node('C'); 
        list.head.next.next.next = new Node('D'); 
        list.head.next.next.next.next = new Node('E'); 
        list.head.next.next.next.next.next = new Node('F'); 
        list.head.next.next.next.next.next.next = new Node('G'); 
  
        list.printlist(head); // print original list 
        list.reorder(head); // rearrange list as per ques 
        System.out.println(""); 
        list.printlist(head); // print modified list 
  
    }
}

Java

How to reorder a linked list in-place

Reorder a linked list in O(n): find its middle, split and reverse the second half, then intertwine both halves.

How to reorder a linked list in-place

Algorithm

Code