CC-13 : Implement pairwise swap of elements of LinkedList.
Description:
Given an input LinkedList, implement pairwise swap of its elements.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
Linked List:
1->2->3->4->
|
Linked List after pairwise swap:
2->1->4->3->
|
Pseudocode:
pairwiseSwap(firstNode):
| If first==null, return first; (base case).
|
| If first.nextNode==null, return first.
|
| Set variable listAfterCurrentPair=first.nextNode.nextNode.
|
| Swap first 2 nodes:
Set newFirst to firstnode.nextNode.
Set newFirst.nextNode to firstNode.
|
| Set first.nextNode to return value of recursive call to pairwiseSwap(listAfterCurrentPair).
|
| Return newFirst.
|
Code:
public LinkedListnode pairwiseSwap(LinkedListnode first){
if (first==null) {return first;}
if (first.nextNode==null) {return first;}
LinkedListnode listAfterCurrentPair=first.nextNode.nextNode;
LinkedListnode newFirst=first.nextNode;
newFirst.nextNode=first;
first.nextNode=pairwiseSwap(listAfterCurrentPair);
return newFirst;
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
public class RecursionPairwiseSwap {
public LinkedListnode pairwiseSwap(LinkedListnode first){
if (first==null) {return first;}
if (first.nextNode==null) {return first;}
LinkedListnode listAfterCurrentPair=first.nextNode.nextNode;
LinkedListnode newFirst=first.nextNode;
newFirst.nextNode=first;
first.nextNode=pairwiseSwap(listAfterCurrentPair);
return newFirst;
}
public static void main(String[] args) {
/************************
Test cases given below:
**********************/
LinkedListnode retVal;
try {
RecursionPairwiseSwap rcn=new RecursionPairwiseSwap();
LinkedListnode first=new LinkedListnode();
first.nodeData=1;
LinkedListnode second=new LinkedListnode();
second.nodeData=2;
LinkedListnode third=new LinkedListnode();
third.nodeData=3;
LinkedListnode fourth=new LinkedListnode();
fourth.nodeData=4;
first.nextNode=second;
second.nextNode=third;
third.nextNode=fourth;
LinkedListnode n=first;
System.out.print("Linked List: ");
while (n !=null) {
System.out.print(n.nodeData+"->");
n=n.nextNode;
}
System.out.println();
retVal=rcn.pairwiseSwap(first);
n=retVal;
System.out.print("Linked List after swap: ");
while (n !=null) {
System.out.print(n.nodeData+"->");
n=n.nextNode;
}
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
exception.printStackTrace();
}
}
}
class LinkedListnode {
int nodeData;
LinkedListnode nextNode=null;
}