REORDER LIST

Concepts Used

Linked List.

Difficulty Level

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.

EXPLANATION:

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 
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); 
    } 
    } 


Previous post FIND PAIR SUM
Next post Check SumTree

Leave a Reply

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