The most efficient way to Pairwise swap elements of a given linked list

Problem Statement

In this problem, we are given a linked list and we have to swap the elements in a pairwise manner. It is not allowed to swap the data, only links should be changed.

Let me explain this with an example - if the linked list is

then the function should change it to

Well, this is one of the most popular questions to be asked in interviews and may seem a bit difficult at first but it is easy to comprehend.

Problem Statement Understanding

Let's first understand the problem statement with the help of an example.
Linked list = 1->2->3->4->5,
The term Pairwise swap indicates that we need to swap the positions of the adjacent two nodes in the linked list.
So,

  • 1->2 will become 2->1
  • 3->4 will become 4->3
  • 5 has no one to be paired with hence it remains as it is.

Finally the linked list will be = 2->1->4->3->5.

Let's take an example with an even length linked list.
Linked list = 4->1->6->3->8->9
So performing pairwise swap,

  • 4->1 will become 1->4.
  • 6->3 will become 3->6.
  • 8->9 will become 9-8.

Finally the linked list will be = 1->4->3->6->9->8.

You should take more examples and get the output according to the above understanding. Analyzing different examples will help you create the logic for this question.

Approach

I hope you got a basic idea on what we need to do to solve this question.
The idea is simple, we have to change the links of the nodes alternatively for every 2 nodes. We will traverse the linked list from the beginning and for every two nodes, we will change the pointers of the next nodes to previous nodes.

Since it is clear what we need to do, take some time and think on how we are going to do it.

Helpful Observations

  1. Since we need to swap two nodes, that is change the links, we should have two pointers pointing on the nodes.

  2. Suppose linked list = &1->2->3->4,and two pointers be prev and curr.

    1. The prev pointing to the node(1) and curr pointing to the node(2).
    2. We can see that we need to change curr->next and point it to prev i.e 2->1.
    3. Also finally the linked list will be 2->1->4->3 i.e. the next of nodes with value 1 will point to the node with value 4, so that means prev->next should be curr->next->next. (Think why this step should be done before step 2).
    4. Step 3 should be done before Step 2 because we need to access node(4) from node(2) but in step 2, node(2)->next is changed to node(1), hence connection to node(4) is lost.
    5. Or we can simply store in temporary node node(2)->next and follow the above steps in given order.
  3. There are some corner conditions to handle, take some examples, use the above observations and try to get those corner conditions.

  4. Below is the proper algorithm for the question.

Algorithm

  • Initialize prev and curr pointers.
  • Traverse the list, store in temp node the value of curr->next and change next of curr as of the prev node.
  • If temp is NULL or temp is the last node then change prev->next to NULL and break the iteration. (Above mentioned corner conditions).
  • Else we have to change next of prev to next of next of curr.
  • Update prev and curr nodes for next iteration.

Code Implementation

The most efficient way to Pairwise swap elements of a given linked list

#include 
using namespace std;
class node {
public:
	int data;
	node* next;
};

node* pairWiseSwap(node* head)
{
	if (head == NULL || head->next == NULL)
		return head;
	node* prev = head;
	node* curr = head->next;
	head = curr;
	while (true) {
		node* temp = curr->next;
		curr->next = prev;
		if (temp == NULL || temp->next == NULL) {
			prev->next = temp;
			break;
		}
		prev->next = temp->next;
		prev = temp;
		curr = prev->next;
	}
	return head;
}
void push(node** head_ref, int new_data)
{
	node* new_node = new node();
	new_node->data = new_data;
	new_node->next = (*head_ref);
	(*head_ref) = new_node;
}
void print(node* node)
{
	while (node != NULL) {
		cout << node->data << " ";
		node = node->next;
	}
}
int main()
{
	node* start = NULL;
	push(&start, 5);
	push(&start, 4);
	push(&start, 3);
	push(&start, 2);
	push(&start, 1);
	start = pairWiseSwap(start);
	print(start);
	return 0;
}

Output: 2 1 4 3 5

Space Complexity: O(1), constant space required as no extra space is used.

In this blog, we have discussed how to swap pairwise nodes and return the modified linked list by changing the links of the nodes directly in the most efficient way. This is a quite popular interview problem and advised to practice this and understand how to solve similar problems. To practice, similar types of problems check out PrepBytes - MYCODE | Contest

Previous post Treemap vs Hashmap vs Linkedhashmap in Java
Next post Iterative Selection Sort For Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *