Last Updated on November 22, 2022 by Prepbytes
In this article, we will discuss different approaches to reorder linked list. Reordering a linked list will always clear the topic like a linked list. And Having knowledge about linked list will make your data structures strong.
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
void reverselist(struct Node** head)
{
// Initialize prev and current pointers
struct Node *prev = NULL, *curr = *head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
// Function to print the linked list
void printlist(struct Node* head)
{
while (head != NULL) {
printf("%d ",head->data);
if (head->next)
printf(" ");
head = head->next;
}
printf("\n");
}
void rearrange(struct Node** head)
{
// 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;
}
struct Node* head1 = *head;
struct Node* head2 = slow->next;
slow->next = NULL;
reverselist(&head2);
*head = newNode(0);
struct 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;
}
}
// Assign the head of the new list to head pointer
*head = (*head)->next;
}
int main()
{ int n;scanf("%d",&n);
int x;scanf("%d",&x);
struct Node* head = newNode(x);
struct Node* headlist=head;
for(int i=1;i<n;i++)
{
scanf("%d",&x);
head->next=newNode(x);
head=head->next;
}
//head->next=NULL;
printf("%d ",headlist->data);
rearrange(&headlist); // Modify the list
printlist(head); // Print modified list
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
void reverselist(Node** head)
{
// Initialize prev and current pointers
Node *prev = NULL, *curr = *head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
// Function to print the linked list
void printlist(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
if (head->next)
cout << " ";
head = head->next;
}
cout << endl;
}
void rearrange(Node** head)
{
// 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;
}
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;
}
}
// Assign the head of the new list to head pointer
*head = (*head)->next;
}
int main()
{ int n;cin>>n;
int x;cin>>x;
Node* head = newNode(x);
Node* headlist=head;
for(int i=1;i<n;i++)
{
cin>>x;
head->next=newNode(x);
head=head->next;
}
//head->next=NULL;
cout<<headlist->data<<" ";
rearrange(&headlist); // Modify the list
printlist(head); // Print modified list
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;
}
}
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
static void arrange(Node head)
{
Deque<Integer> deque = new ArrayDeque<>();
Node temp = head;
while(temp != null)
{
deque.addLast(temp.data);
temp = temp.next;
}
temp = head;
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();
Node head = new Node(x);
Node headlist=head;
for(int i=1;i<n;i++)
{
x = sc.nextInt();
head.next=new Node(x);
head=head.next;
}
arrange(headlist);
printList(headlist);
}
}
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 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)
In this article, we have discussed multiple approaches to reorder the given linked list. Practicing “reorder the given linked list” will help you to understand linked lists in detail. To practice more problems on Linked List you can check out MYCODE | Competitive Programming.
FAQ
1. What defines an ordered list?
An ordered list defines a list of items in which the order of the items matters.
2. How do you swap data between two nodes in a linked list?
The idea is to first search x and y in the given linked list. If any of them is not present, then return. While searching for x and y, keep track of current and previous pointers. First change next of previous pointers, then change next of current pointers.
3. What is a linked list in data structure?
A linked list is the most sought-after data structure when it comes to handling dynamic data elements. A linked list consists of a data element known as a node. And each node consists of two fields: one field has data, and in the second field, the node has an address that keeps a reference to the next node.