Home » Interview Questions » LinkedList Interview Questions » Rearrange a given linked list in-place

Rearrange a given linked list in-place


()

Given a singly linked list L0-> L1-> … -> Ln-1-> Ln. Rearrange the nodes in the list so that the new formed list is : L0-> Ln-> L1-> Ln-1-> L2-> Ln-2…

Example

INPUT :
1->2 ->3 ->4 ->5

OUTPUT :
1 ->5 ->2 ->4 ->3

Time Complexity : O(n)

Algorithm

1. Find the middle point using tortoise and hare method
    a. Take two variables slow, fast. Move fast two steps ahead and move slow only one step ahead for every iteration.

     b. By the end of the list, slow will point to the middle point of the linkedlist

2. Split the linked list into two halves using the middle point

3. Reverse the second half

4. Do alternate merge of first and second halves

Implementation of Algorithm for above example

1. Middle point is the node 3

2. list1 = 1->2->3, list2 = 4->5

3. Reverse the second list.
list1 = 1->2->3, list2 = 5->4

4. Alternate Merge
result = 1 ->5 ->2 ->4 ->3

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LLNode{
	int data;
	LLNode *next;	
};
// Function to create newNode in a linkedlist
LLNode* newNode(int data)
{
    LLNode *temp = new LLNode;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
// Function to reverse the linked list
void reverselist(LLNode **head)
{
    // Initialize prev and current pointers
    LLNode *prev = NULL, *curr = *head, *next;
 
    while (curr)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
 
    *head = prev;
}
// Function to rearrange a linked list
void rearrange(LLNode **head)
{
    // 1) Find the middle point using tortoise and hare method 
    LLNode *slow = *head, *fast = slow->next;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
 
    // 2) Split the linked list in two halves
    LLNode *list1 = *head;
    LLNode *list2 = slow->next;
    slow->next = NULL;
 
    // 3) Reverse the second half
    reverselist(&list2);
 
    // 4) Merge alternate nodes
    *head = newNode(0); // Assign dummy Node
 
    // curr is the pointer to this dummy Node, which will
    // be used to form the new list
    LLNode *result = *head;
    while (list1 || list2)
    {
        // First add the element from first list
        if (list1)
        {
            result->next = list1;
            result = result->next;
            list1 = list1->next;
        }
 
        // Then add the element from second list
        if (list2)
        {
            result->next = list2;
            result = result->next;
            list2 = list2->next;
        }
    }
    // Assign the head of the new list to head pointer
    *head = (*head)->next;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	LLNode*curr=new LLNode;
	//make a new node with this data and next pointing to NULL
	curr->data=dataToBeInserted;
	curr->next=NULL;

	if(*head==NULL) //if list is empty then set the current formed node as head of list
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}


void display(LLNode**head)
{
	LLNode*temp=*head;
	while(temp!=NULL) //till the list ends (NULL marks ending of list)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}

int main() 
{    
	
	LLNode *head = NULL; //initial list has no elements

	insertAtBeginning(&head,5);
	insertAtBeginning(&head,4);
	insertAtBeginning(&head,3);
	insertAtBeginning(&head,2);
	insertAtBeginning(&head,1);
	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	rearrange(&head);
	cout<<"After rearranging the elements"<<endl;
	display(&head);
	return 0;
}

READ  Merge K Sorted Linked Lists

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions