# Reorder List

Back to home
Logicmojo - Updated Aug 28, 2021

## Problem Statement: Reorder List

Given a single linked list L0 -> L1 ->... -> Ln-1 -> Ln.Rearrange the nodes in the list to generate the following new list: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2...
This must be done in place, with no changes to the nodes' values.

Input Format
The first line contains an integer N , denoting the number of elements in the linked list.
The second line contains N numbers separated by space.

Output Format
You have to print the linked list in mention above order.

Example
Input
4
1 3 5 7

Output
1 7 3 5

Explanation
Given [1,3,5,7] reorder it to [1,7,3,5].

We have presented two approaches to find the two elements:

• Simple Approach
• Efficient Approach

### Simple Approach

1. Set the current node to be the head.

2. If the next of current node is not null, do the following:

1. Find the last node, remove it from the end, and replace it with the next of current node.

2. Change the current to the next to next of the current.

The time complexity of the above simple solution is O(n^2) where n is the number of nodes in the linked list.

### Efficient Approach

Algorithm

1. The tortoise and hare approach can be used to find the centre point.

2. Using the middle point identified in step 1, divide the linked list into two halves.

3. Reverse the second half.

4. Merge the first and second halves alternately.

The Time Complexity of this solution is O(n).

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

struct Node {
int data;
struct Node* next;
};

Node* newNode(int 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 << head->data << " ";
cout << "-> ";
}
cout << endl;
}

{
Node *slow = *head, *fast = slow->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

slow->next = NULL;

curr = curr->next;
}

curr = curr->next;
}
}

}

int main()
{

return 0;
}
```

Java Implementation:

```class LinkedList {

static class Node {

int data;
Node next;

Node(int d)
{
data = d;
next = null;
}
}

void printlist(Node node)
{
if (node == null) {
return;
}
while (node != null) {
System.out.print(node.data + " -> ");
node = node.next;
}
}

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 rearrange(Node node)
{

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

Node node1 = node;
Node node2 = slow.next;
slow.next = null;

node2 = reverselist(node2);

node = new Node(0);
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)
{

System.out.println("");
}
}
```

Python Implementation:

```class Node:

def __init__(self, d):
self.data = d
self.next = None

def printlist(node):
if(node == None):
return
while(node != None):
print(node.data," -> ", end = "")
node = node.next

def reverselist(node):
prev = None
curr = node
next=None
while (curr != None):
next = curr.next
curr.next = prev
prev = curr
curr = next
node = prev
return node

def rearrange(node):

slow = node
fast = slow.next
while (fast != None and fast.next != None):
slow = slow.next
fast = fast.next.next

node1 = node
node2 = slow.next
slow.next = None

node2 = reverselist(node2)

node = Node(0) #Assign dummy Node

curr = node

while (node1 != None or node2 != None):

if (node1 != None):
curr.next = node1
curr = curr.next
node1 = node1.next

if(node2 != None):
curr.next = node2
curr = curr.next
node2 = node2.next

node = node.next