Related Tags

reordering
alternative

# How to reorder a linked list in-place

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.

Original list
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;
}

{
Node *prev = NULL, *curr = *head, *next;

while (curr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}

}

{
cout<<"| ";
{
cout << head->data << " ";
if(head->next) cout << "| ---> | ";
}
cout << "|" << endl;
}

{
//Locating the middle point
Node *p1 = *head, *p2 = p1->next;
while (p2 && p2->next)
{
p1 = p1->next;
p2 = p2->next->next;
}

p1->next = NULL;

//Reverse the second half

//Merge alternate nodes

{
{
curr = curr->next;
}

{
curr = curr->next;
}
}

}

int main()
{

} 

RELATED TAGS