Reorder List

Name: Merge Overlapping Intervals
Brand: LogicMojo
SKU: .
Availability: InStock
Rating: 4.8 (230 reviews)

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: Reorder List
Simple Approach
Efficient Approach

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

Set the current node to be the head.
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

The tortoise and hare approach can be used to find the centre point.
Using the middle point identified in step 1, divide the linked list into two halves.
Reverse the second half.
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;
}

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)
{
	while (head != NULL) {
		cout << head->data << " ";
		if (head->next)
			cout << "-> ";
		head = head->next;
	}
	cout << endl;
}

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

	Node* head1 = *head;
	Node* head2 = slow->next;
	slow->next = NULL;

	reverselist(&head2);

	*head = newNode(0); 
	Node* curr = *head;
	while (head1 || head2) {
		if (head1) {
			curr->next = head1;
			curr = curr->next;
			head1 = head1->next;
		}

		if (head2) {
			curr->next = head2;
			curr = curr->next;
			head2 = head2->next;
		}
	}

	*head = (*head)->next;
}

int main()
{
	Node* head = newNode(1);
	head->next = newNode(2);
	head->next->next = newNode(3);
	head->next->next->next = newNode(4);
	head->next->next->next->next = newNode(5);

	printlist(head);
	rearrange(&head);
	printlist(head); 
	return 0;
}

Java Implementation:

class LinkedList {

	static Node head;

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

		LinkedList list = new LinkedList();
		list.head = new Node(1);
		list.head.next = new Node(2);
		list.head.next.next = new Node(3);
		list.head.next.next.next = new Node(4);
		list.head.next.next.next.next = new Node(5);

		list.printlist(head); 
		list.rearrange(head); 
		System.out.println("");
		list.printlist(head); 
	}
}

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

head = None
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

printlist(head) 
rearrange(head) 
print()
printlist(head)

Time Complexity: O(N) .

Space Complexity: O(1)

With this article at Logicmojo, you must have the complete idea of solving Reorder List problem.