Pairwise swapping in linked list

Given a linked list, write a program to swap the elements pairwise

Here, pairwise swaping means swaping the first two elements and the next two elements and so on till the end of the linked list

Example

Input : 6->16->15->50->1->23->49
Output : 16->6->50->15->23->1->49

In the above example, we swaped 6, 16 and 15, 50 and 1, 23.

In this method, we will traverse the linked list. While traversing the linked list, we will swap the current node with the next node.

Time Complexity : O(n)

Algorithm

1. Create a temp pointer, which is initialized to the head
2. Till temp and temp's next node is not equal to Null, swap the elements in temp and temp next node, and move the temp pointer two steps ahead in the linked list

C++ Program

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

struct LL{
	int data;
	LL *next;	
};

void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL*temp=*head,*curr=new LL;
			curr->data=dataToBeInserted;
			curr->next=NULL;
	if(*head==NULL)
			*head=curr;
		
	else
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}

void swap(int &a,int &b)
{
	int temp = a;
	a = b;
	b = temp;
}


void pairwiseSwap(struct LL **head)
{
	struct LL * temp = *head;
	
	while(temp and temp->next != NULL)
	{
		swap(temp->data , temp->next->data);
		temp = temp->next->next;
	}
	
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			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()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,73);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,62);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,116);
	insertAtBeginning(&head,982); //comment this line to check for both odd and even length lists.
	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	
	pairwiseSwap(&head);
	
	cout<<"\nAfter pairwise swapping the list becomes :-\n";
	display(&head);
	
	return 0;
}
Try It


Next > < Prev
Scroll to Top