Pairwise Swap Elements of a Singly Linked List
Introduction
This article will discuss the problem of finding the problem “Pairwise Swap Elements of a Singly Linked List” and its solution. Before jumping into the details of the problem and approach to solve it, you need to know about the linked list data structure.
Now, let’s understand the problem. In this problem, a singly linked list is given, and we have to pairwise swap elements of the given linked list.
Let’s make it clear by taking an example
Assume the given linked list is : 1 > 4 > 5 > 9 > 8 > 5 > 2 > NULL
After swapping pairwise, the given linked list will get changed int
4 > 1 > 9 > 5 > 5 > 8 > 2 > NULL
Note here that the number of elements is odd, so the last element ‘2’ can’t be paired with any other element and it won’t be swapped with any other element.
Iterative Solution Approach
We have been given a singly linked list and we have to pairwise swap elements of this given linked list. The idea is to start traversing the linked list from its first node and swap its data with the next node and then move to the node which is next to its next node to consider the next pair.
Let’s use the above example to understand run this algorithm:
Algorithm 
Step 1. Create a class ‘Node’ for creating the linked lists.
Step 2. Then create the function “pairwiseSwap()” to pairwise swap elements of a singly linked list, which will accept one parameter  pointer to the head node of the given linked list.
Step 3. Initialize two node pointers to point the first node and second node of the liked list and using these node pointers traverse each pair of the given linked list and while traversing swap the data of the two nodes of each pair.
Step 4. Finally, after traversing all the possible pairs in the linked list, return the head node of the new linked list generated by the pairwise swapping.
C++ code:


Algorithm Complexity:
Time Complexity: O(N)
In the function “pairwise Swap()” created to pairwise swap elements of a linked list, we have created a “while loop” to traverse all the nodes of the given linked list. So, the time complexity is O(N), where ‘N’ is the number of nodes in the given linked list.
Space Complexity: O(1)
As we have used constant space, so the space complexity is O(1)
Recursive Solution Approach
The idea behind this approach is the same as the previous approach. But here instead of traversing iteratively one by one each pair, we will call a recursive function. The recursive function will swap the data of the current node and its next node and then if a next pair exists, then the function will call itself for the next pair. In this way, the function will keep calling itself recursively up to the last possible pair in the linked list.
Algorithm 
Step 1. Create a class ‘Node’ for creating the linked lists.
Step 2. Then create the recursive function “pairwiseSwap()” to pairwise swap elements of a linked list recursively, which will accept one parameter  pointer to the head node of the given linked list.
Step 3. If the head node and its next node are not NULL, then swap their elements and recursively call the function for the next pair.
Step 4. Finally, after all the recursive calls, print the linked list generated by pairwise swapping.
C++ code:


Algorithm Complexity:
Time Complexity: O(N)
The function “pairwiseSwap()” created to pairwise swap elements, will be called for each pair of nodes and one call will take constant time. So, the time complexity is O(N).
Space Complexity: O(1)
As we have used constant space, so the space complexity is O(1)
Frequently asked questions
 What is a linked list?
A linked list is a linear data structure that is formed by connected nodes. Each node has a value associated with it and the pointer(s) to its directly connected node(s).
 What is the key difference between a singly linked list and a doublylinked list?
A singlylinked list is unidirectional, which means that the node of a singly linked list contains the pointer to its next node only. In contrast, a doublylinked list is bidirectional, and its node contains the pointer to its next and previous nodes.
 Which approach iterative or recursive is better to be considered?
In the recursive function, function calls are stored in the stack and so if the number of nodes will be larger, we can get a “stackoverflow” error. Thus the iterative approach is better to be considered.
Key takeaways
This article discussed the problem of finding the problem “Pairwise Swap Elements of a Singly Linked List”, iterative and recursive approaches to solve the problem, their C++ implementation, and their time and space complexities. If you want to practice problems on a linked list, then you can visit codestudio.
If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.
Until then, All the best for your future endeavors, and Keep Coding.
Comments
No comments yet
Be the first to share what you think