Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

linked list
reordering
alternative

How to reorder a linked list in-place

Educative Answers Team

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

svg viewer
Original list
svg viewer
Reordered list

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.
1 of 8

Code

#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);
} 

RELATED TAGS

linked list
reordering
alternative
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring