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…  


1->2 ->3 ->4 ->5

1 ->5 ->2 ->4 ->3

Time Complexity : O(n)


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.

Please click Like if you loved this article?

     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
    // 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

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

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

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

	cout<<"\nCurrent List is :-\n";
	cout<<"After rearranging the elements"<<endl;
	return 0;

See also
Reverse Nodes in K-Group


Please click Like if you loved this article?