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
Python Programming:
# Python program to swap the elements of linked list pairwise
# Node class
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to pairwise swap elements of a linked list
def pairwiseSwap(self):
temp = self.head
# There are no nodes in ilnked list
if temp is None:
return
# Traverse furthur only if there are at least two
# left
while(temp is not None and temp.next is not None):
# Swap data of node with its next node's data
temp.data, temp.next.data = temp.next.data, temp.data
# Move temo by 2 fro the next pair
temp = temp.next.next
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Utility function to prit the linked LinkedList
def printList(self):
temp = self.head
while(temp):
print temp.data,
temp = temp.next
# Driver program
llist = LinkedList()
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
print "Linked list before calling pairWiseSwap() "
llist.printList()
llist.pairwiseSwap()
print "\nLinked list after calling pairWiseSwap()"
llist.printList()
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
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.
Python Programming:
/* Recursive function to pairwise swap elements of a linked list */
void pairWiseSwap(struct node *head)
{
/* There must be at-least two nodes in the list */
if (head != NULL && head->next != NULL)
{
/* Swap the node's data with data of next node */
swap(&head->data, &head->next->data);
/* Call pairWiseSwap() for rest of the list */
pairWiseSwap(head->next->next);
}
}
Time complexity: O(n)