REORDER LIST

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.

Leave a Reply

Your email address will not be published. Required fields are marked *