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

 

Translate »