# REORDER LIST

Hard.

#### Problem Statement :

Given a singly linked list `L:L0→L1→…→Ln−1→Ln`,
reorder it to `:L0→Ln→L1→Ln−1→L2→Ln−2→…`
You must do this in-place without altering the nodes’ values.
Expected Time Complexity O`(`n`)`.

See original problem statement here

#### Example:

`````` Given 1->2->3->4,
reorder it to 1->4->2->3.``````

## Approach 1`(Brute force)`:

Go through the best online course for data structures and algorithms and Initialize the current node as head.

While next of current node is not null,find the last node, remove it from the end and insert it as next of the current node.

Move current to next of current.

TIME COMPLEXITY: O`(`n*n`)`

## Approach 2`(Efficient solution):`

This approach uses two pointers(tortoise and hare method) to find the middle of linked list.Reverse the second half and alternately merge the first and second halves.

## Approach 3`(Deque):`

1) Create an empty deque.

2) Insert all element from the linked list to the deque.

3) Insert the element back to the linked list from deque in alternate fashion i.e first then last and so on.

## SOLUTIONS:

```#include <stdio.h>
#include<stdlib.h>
struct Node {
int data;
struct Node* next;
};

// Function to create newNode in a linkedlist
struct Node* newNode(int key)
{
struct Node* temp;
temp=(struct Node *)malloc(sizeof(struct Node));
temp->data = key;
temp->next = NULL;
return temp;
}

// Function to reverse the linked list
{
// Initialize prev and current pointers
struct Node *prev = NULL, *curr = *head, *next;

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

}

// Function to print the linked list
{
printf(" ");
}
printf("\n");
}

{
// 1) Find the middle point using tortoise and hare method
struct 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()
{   int n;scanf("%d",&n);
int x;scanf("%d",&x);

for(int i=1;i<n;i++)
{
scanf("%d",&x);
}
return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};

// Function to create newNode in a linkedlist
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}

// Function to reverse the linked list
{
// Initialize prev and current pointers
Node *prev = NULL, *curr = *head, *next;

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

}

// Function to print the linked list
{
cout << head->data << " ";
cout << " ";
}
cout << endl;
}

{
// 1) Find the middle point using tortoise and hare method
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()
{   int n;cin>>n;
int x;cin>>x;

for(int i=1;i<n;i++)
{
cin>>x;
}
return 0;
}
```
```import java.util.*;
import java.lang.*;
import java.io.*;

class prepbytes
{
static class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
next = null;
}
}
{
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
{
Deque<Integer> deque = new ArrayDeque<>();
while(temp != null)
{
temp = temp.next;
}
int i = 0;
while(!deque.isEmpty())
{
if(i % 2 == 0)
{
temp.data = deque.removeFirst();
}
else
{
temp.data = deque.removeLast();
}
i++;
temp = temp.next;
}
}
public static void main (String[] args)
{ Scanner sc = new Scanner(System.in);
int n= sc.nextInt();
int x = sc.nextInt();