Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

REORDER LIST

Last Updated on November 22, 2022 by Prepbytes

How to Reorder List

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.``````

Approaches to Reorder List

Approach 1(Brute force) To Reorder The Given Linked List:

1) Initialize the current node as head.

2) 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.

3) Move current to next of current.

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

Approach 2 (Efficient solution) To Reorder The Given Linked List:

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) To Reorder The Given Linked List:

1) Create an empty deque.

2) Insert all elements 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.

Code implementations

```#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();
for(int i=1;i<n;i++)
{
x = sc.nextInt();
}

}
}

```
```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)

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

print()
```