Pairwise swap elements of a given linked list by chnaging links

Given a singly linked list, write a function to swap elements pairwise. In the below methods the main idea is to swap links rather than swapping the data.

Example

INPUT :
23 ->1 ->50 ->15 ->16 ->6

OUTPUT :
1 ->23 ->15 ->50 ->6 ->16

In the above example we can see that the elements are swaped pairwise ie, (1,23), (50,15) and (16,6)

Method 1 :

Time Complexity : O(n)

Algorithm

Initialize "prev" and "curr" pointers to head and head's next and change the head to "curr"
Till the end of the list

1. Initialize "next" pointer to "curr's" next and change next of "curr" as previous node
    ie,  changing the direction of the link

2. Change next of "prev" to "next" next ie, skipping two nodes

3. Update "prev" and "curr" to "next" and "prev" next respectively

The above Algorithm can be clearly explained in below diagram

C++ Program

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

struct LLNode{
	int data;
	LLNode *next;	
};
//This funnction will swap the elements pairwise
void pairwiseSwap(LLNode** head)
{
  	// If linked list is empty or there is only one node in list
    if (*head == NULL || (*head)->next == NULL)
        return;
 
    // Initialize previous and current pointers
    LLNode *prev = *head;
    LLNode *curr = (*head)->next;
 
    *head = curr;  // Change head before proceeeding
 
    // Traverse the list
    while (true)
    {
        LLNode *next = curr->next;
        curr->next = prev; // Change next of current as previous node
 
        // If next NULL or next is the last node
        if (next == NULL || next->next == NULL)
        {
            prev->next = next;
            break;
        }
 
        // Change next of previous to next next
        prev->next = next->next;
 
        // Update previous and curr
        prev = next;
        curr = prev->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,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);

	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	pairwiseSwap(&head);
	cout<<"After doing PairWise Swap"<<endl;
	display(&head);
	return 0;
}
Try It

Method 2

Recursive Implementation

Algorithm

Change the links for first two nodes

1. Store the head of the list after two nodes ie, temp = head->next->next

2. Store head next in "newhead" pointer ie, newhead = head->next

3. change next of second node ie, head->next->next = head
    Make the recursive call to the rest of the list

C++ Program

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

struct LLNode{
	int data;
	LLNode *next;	
};
//This funnction will swap the elements pairwise
LLNode* pairwiseSwap(LLNode* head)
{
  	// If the list is empty or has only one node
    if (head == NULL || head->next == NULL)
        return head;
 
    // Store head of list after two nodes
    LLNode* temp = head->next->next;
 
    // Store head next
    LLNode* newhead = head->next;
 
    // Change next of second node
    head->next->next = head;
 
    // Recur for remaining list and change next of head
    head->next = pairwiseSwap(temp);
 
    // Return new head of modified list
    return newhead;
}
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,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);

	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	result = pairwiseSwap(head);
	cout<<"After doing PairWise Swap"<<endl;
	display(&result);
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top