Rearrange a linked list such that all even and odd position nodes are together

Given  a linked list, write a function such that all the even position nodes are together and all the odd position nodes are together

Example

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

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

In this method we will modify the given input list

Algorithm

1. Initialize "odd_list" and "even_list" pointers to the first odd node and first even node respectively

2. If there are no more elements left, then connect odd_list and even_list and break the loop.

3. Connect the odd nodes
    odd_list->next = even_list->next;
            odd_list = even_list->next;

4. If there are no even nodes left, then connect the odd list and even list and break the loop

5. Connect the even nodes
    even_list->next = odd_list->next;
            even_list = odd_list->next;

C++ Program

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

struct LLNode{
	int data;
	LLNode *next;	
};
//Rearranges list such that all odd positioned nodes
//are before even positioned nodes
LLNode *evenoddTogether(LLNode *head)
{
    // If no elments
    if (head == NULL)
        return NULL;
 
    // Initialize first nodes of even and
    // odd lists
    LLNode *odd_list = head;
    LLNode *even_list = head->next;
 
    //to connect even list, we need to remember the even list start
    LLNode *even_list_start = even_list;
  

    while (1)
    {
        //If there are no nodes left, then connect even list to odd list
        if (!odd_list || !even_list || !(even_list->next))
        {
            odd_list->next = even_list_start;
            break;
        }
 
        // Connecting odd nodes
        odd_list->next = even_list->next;
        odd_list = even_list->next;
 
        // If there are NO more even nodes after
        // current odd.
        if (odd_list->next == NULL)
        {
            even_list->next = NULL;
            odd_list->next = even_list_start;
            break;
        }
 
        // Connecting even nodes
        even_list->next = odd_list->next;
        even_list = odd_list->next;
    }
 
    return head;
}
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
	LLNode *result = NULL;
	insertAtBeginning(&head,5);
	insertAtBeginning(&head,4);
	insertAtBeginning(&head,3);
	insertAtBeginning(&head,2);
	insertAtBeginning(&head,1);
	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	result = evenoddTogether(head);
	cout<<"After rearranging even and odd nodes together"<<endl;
	display(&result);
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top