Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5 then the function should change it to 2->1->4->3->5, and if the linked list is 1->2->3->4->5->6 then the function should change it to 2->1->4->3->6->5.
METHOD 1 (Iterative)
Start from the head node and traverse the list. While traversing swap data of each node with its next node’s data
Start from the head node and traverse the list. While traversing swap data of each node with its next node’s data
Java Programming:
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20pairwise%20swap%20elements%20of%20a%20linked%20list%0Aclass%20LinkedList%0A%7B%0A%20%20%20%20Node%20head%3B%20%20%2F%2F%20head%20of%20list%0A%20%20%0A%20%20%20%20%2F*%20Linked%20list%20Node*%2F%0A%20%20%20%20class%20Node%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%3B%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7Bdata%20%3D%20d%3B%20next%20%3D%20null%3B%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20void%20pairWiseSwap()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Traverse%20only%20till%20there%20are%20atleast%202%20nodes%20left%20*%2F%0A%20%20%20%20%20%20%20%20while%20(temp%20!%3D%20null%20%26%26%20temp.next%20!%3D%20null)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20Swap%20the%20data%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20k%20%3D%20temp.data%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp.data%20%3D%20temp.next.data%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp.next.data%20%3D%20k%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next.next%3B%0A%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%2F*%20Utility%20functions%20*%2F%0A%20%0A%20%20%20%20%2F*%20Inserts%20a%20new%20Node%20at%20front%20of%20the%20list.%20*%2F%0A%20%20%20%20public%20void%20push(int%20new_data)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%201%20%26%202%3A%20Allocate%20the%20Node%20%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Put%20in%20the%20data*%2F%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F*%203.%20Make%20next%20of%20new%20Node%20as%20head%20*%2F%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F*%204.%20Move%20the%20head%20to%20point%20to%20new%20Node%20*%2F%0A%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Function%20to%20print%20linked%20list%20*%2F%0A%20%20%20%20void%20printList()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20while%20(temp%20!%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20System.out.print(temp.data%2B%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%3B%0A%20%20%20%20%20%20%20%20%7D%20%20%0A%20%20%20%20%20%20%20%20System.out.println()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20llist%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Created%20Linked%20List%201-%3E2-%3E3-%3E4-%3E5%20*%2F%0A%20%20%20%20%20%20%20%20llist.push(5)%3B%0A%20%20%20%20%20%20%20%20llist.push(4)%3B%0A%20%20%20%20%20%20%20%20llist.push(3)%3B%0A%20%20%20%20%20%20%20%20llist.push(2)%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Linked%20List%20before%20calling%20pairWiseSwap()%20%22)%3B%0A%20%20%20%20%20%20%20%20llist.printList()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20llist.pairWiseSwap()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Linked%20List%20after%20calling%20pairWiseSwap()%20%22)%3B%0A%20%20%20%20%20%20%20%20llist.printList()%3B%0A%20%20%20%20%7D%0A%7D%20%0A%2F*%20This%20code%20is%20contributed%20by%20Rajat%20Mishra%20*%2F” message=”” highlight=”” provider=”manual”/]
Output:
Linked List before calling pairWiseSwap() 1 2 3 4 5 Linked List after calling pairWiseSwap() 2 1 4 3 5
Time complexity: O(n)
METHOD 2 (Recursive)
If there are 2 or more than 2 nodes in Linked List then swap the first two nodes and recursively call for rest of the list.
Java Programming:
[pastacode lang=”java” manual=”%2F*%20Recursive%20function%20to%20pairwise%20swap%20elements%20of%20a%20linked%20list%20*%2F%0Avoid%20pairWiseSwap(struct%20node%20*head)%0A%7B%0A%20%20%2F*%20There%20must%20be%20at-least%20two%20nodes%20in%20the%20list%20*%2F%0A%20%20if%20(head%20!%3D%20NULL%20%26%26%20head-%3Enext%20!%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20%20%20%2F*%20Swap%20the%20node’s%20data%20with%20data%20of%20next%20node%20*%2F%0A%20%20%20%20%20%20swap(%26head-%3Edata%2C%20%26head-%3Enext-%3Edata)%3B%0A%20%20%20%20%0A%20%20%20%20%20%20%2F*%20Call%20pairWiseSwap()%20for%20rest%20of%20the%20list%20*%2F%0A%20%20%20%20%20%20pairWiseSwap(head-%3Enext-%3Enext)%3B%0A%20%20%7D%20%20%0A%7D” message=”” highlight=”” provider=”manual”/]
Time complexity: O(n)