Pairwise swap elements of a given linked list
Given a singly linked list, write a function to swap elements pairwise.
Input : 1->2->3->4->5->6->NULL
Output : 2->1->4->3->6->5->NULLInput : 1->2->3->4->5->NULL
Output : 2->1->4->3->5->NULLInput : 1->NULL
Output : 1->NULL
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 then the function should change it to.
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
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.
Below is the implementation of the above approach:
C++
// C++ program to pairwise swap elements // in a given linked list #include <bits/stdc++.h> using namespace std; /* A linked list node */ class Node { public: int data; Node* next; }; /* Function to pairwise swap elements of a linked list */ void pairWiseSwap(Node* head) { Node* temp = head; /* Traverse further only if there are at-least two nodes left */ while (temp != NULL && temp->next != NULL) { /* Swap data of node with its next node's data */ swap(temp->data, temp->next->data); /* Move temp by 2 for the next pair */ temp = temp->next->next; } } /* Function to add a node at the beginning of Linked List */ void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } // Driver Code int main() { Node* start = NULL; /* The constructed linked list is: 1->2->3->4->5 */ push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); cout << "Linked list " << "before calling pairWiseSwap()\n"; printList(start); pairWiseSwap(start); cout << "\nLinked list " << "after calling pairWiseSwap()\n"; printList(start); return 0; } // This code is contributed // by rathbhupendra |
C
/* C program to pairwise swap elements in a given linked list */ #include <stdio.h> #include <stdlib.h> /* A linked list node */ struct Node { int data; struct Node* next; }; /*Function to swap two integers at addresses a and b */ void swap(int* a, int* b); /* Function to pairwise swap elements of a linked list */ void pairWiseSwap(struct Node* head) { struct Node* temp = head; /* Traverse further only if there are at-least two nodes left */ while (temp != NULL && temp->next != NULL) { /* Swap data of node with its next node's data */ swap(&temp->data, &temp->next->data); /* Move temp by 2 for the next pair */ temp = temp->next->next; } } /* UTILITY FUNCTIONS */ /* Function to swap two integers */ void swap(int* a, int* b) { int temp; temp = *a; *a = *b; *b = temp; } /* Function to add a node at the beginning of Linked List */ void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(struct Node* node) { while (node != NULL) { printf("%d ", node->data); node = node->next; } } /* Driver program to test above function */ int main() { struct Node* start = NULL; /* The constructed linked list is: 1->2->3->4->5 */ push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); printf("Linked list before calling pairWiseSwap()\n"); printList(start); pairWiseSwap(start); printf("\nLinked list after calling pairWiseSwap()\n"); printList(start); return 0; } |
Java
// Java program to pairwise swap elements of a linked list class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; Node(int d) { data = d; next = null; } } void pairWiseSwap() { Node temp = head; /* Traverse only till there are atleast 2 nodes left */ while (temp != null && temp.next != null) { /* Swap the data */ int k = temp.data; temp.data = temp.next.data; temp.next.data = k; temp = temp.next.next; } } /* Utility functions */ /* Inserts a new Node at front of the list. */ public void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Function to print linked list */ void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } /* Driver program to test above functions */ public static void main(String args[]) { LinkedList llist = new LinkedList(); /* Created Linked List 1->2->3->4->5 */ llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); System.out.println("Linked List before calling pairWiseSwap() "); llist.printList(); llist.pairWiseSwap(); System.out.println("Linked List after calling pairWiseSwap() "); llist.printList(); } } /* This code is contributed by Rajat Mishra */ |
Python
# 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 linked list if temp is None: return # Traverse furthethr only if there are at least two # left while(temp and temp.next): # If both nodes are same, # no need to swap data if(temp.data != temp.next.data): # Swap data of node with its next node's data temp.data, temp.next.data = temp.next.data, temp.data # Move temp by 2 to 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 print 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) |
C#
// C# program to pairwise swap elements of a linked list using System; class LinkedList { Node head; // head of list /* Linked list Node*/ public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } void pairWiseSwap() { Node temp = head; /* Traverse only till there are atleast 2 nodes left */ while (temp != null && temp.next != null) { /* Swap the data */ int k = temp.data; temp.data = temp.next.data; temp.next.data = k; temp = temp.next.next; } } /* Utility functions */ /* Inserts a new Node at front of the list. */ public void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Function to print linked list */ void printList() { Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.WriteLine(); } /* Driver program to test above functions */ public static void Main(String[] args) { LinkedList llist = new LinkedList(); /* Created Linked List 1->2->3->4->5 */ llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); Console.WriteLine("Linked List before calling pairWiseSwap() "); llist.printList(); llist.pairWiseSwap(); Console.WriteLine("Linked List after calling pairWiseSwap() "); llist.printList(); } } // This code is contributed by Arnab Kundu |
Javascript
<script> // JavaScript program to pairwise swap // elements of a linked list var head; // head of list /* Linked list Node */ class Node { constructor(val) { this.data = val; this.next = null; } } function pairWiseSwap() { var temp = head; /* Traverse only till there are atleast 2 nodes left */ while (temp != null && temp.next != null) { /* Swap the data */ var k = temp.data; temp.data = temp.next.data; temp.next.data = k; temp = temp.next.next; } } /* Utility functions */ /* Inserts a new Node at front of the list. */ function push(new_data) { /* * 1 & 2: Allocate the Node & Put in the data */ var new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Function to print linked list */ function printList() { var temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } document.write("<br/>"); } /* Driver program to test above functions */
/* Created Linked List 1->2->3->4->5 */ push(5); push(4); push(3); push(2); push(1); document.write( "Linked List before calling pairWiseSwap() <br/>" ); printList(); pairWiseSwap(); document.write( "Linked List after calling pairWiseSwap()<br/> " ); printList(); // This code is contributed by todaysgaurav </script> |
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 the rest of the list.
Below image is a dry run of the above approach:
Below is the implementation of the above approach:
C
/* 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); } } |
Java
/* Recursive function to pairwise swap elements of a linked list */ static void pairWiseSwap(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); } } // This code contributed by aashish2995 |
Python3
# Recursive function to pairwise swap elements of a linked list def pairWiseSwap(head): # There must be at-least two nodes in the list if (head != None and head.next != None):
# 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); # This code is contributed by _saurabh_jaiswal |
C#
/* Recursive function to pairwise swap elements of a linked list */ static void pairWiseSwap(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); } } // This code contributed by aashish2995 |
Javascript
<script> /* Recursive function to pairwise swap elements of a linked list */ function pairWiseSwap(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); } } // This code is contributed by avanitrachhadiya2155 </script> |
Time complexity: O(n)
The solution provided there swaps data of nodes. If data contains many fields, there will be many swap operations. See this for an implementation that changes links rather than swapping data.
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.
Article Tags :
Linked List
Amazon
Microsoft
Moonfrog Labs
Practice Tags :
Moonfrog Labs
Amazon
Microsoft
Linked List
Read Full Article
Pairwise swap elements of a given linked list by changing links
Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5->6->7 then the function should change it to 2->1->4->3->6->5->7, 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
This problem has been discussed here. The solution provided there swaps data of nodes. If data contains many fields, there will be many swap operations. So changing links is a better idea in general. Following is the implementation that changes links instead of swapping data.
C++
/* This program swaps the nodes of linked list rather than swapping the field from the nodes. Imagine a case where a node contains many fields, there will be plenty of unnecessary swap calls. */ #include <bits/stdc++.h> using namespace std; /* A linked list node */ class node { public: int data; node* next; }; /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ node* pairWiseSwap(node* head) { // If linked list is empty or // there is only one node in list if (head == NULL || head->next == NULL) return head;
// Initialize previous and current pointers node* prev = head; node* curr = head->next;
head = curr; // Change head before proceeding
// Traverse the list while (true) { node* next = curr->next; curr->next = prev; // Change next of // current as previous node
// If next NULL or next is the last node if (next == NULL || next->next == NULL) { prev->next = next; break; }
// Change next of previous to next of next prev->next = next->next;
// Update previous and curr prev = next; curr = prev->next; } return head; } /* Function to add a node at the beginning of Linked List */ void push(node** head_ref, int new_data) { /* allocate node */ node* new_node = new node(); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } /* Driver code */ int main() { node* start = NULL; /* The constructed linked list is: 1->2->3->4->5->6->7 */ push(&start, 7); push(&start, 6); push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); cout << "Linked list before " << "calling pairWiseSwap() "; printList(start); start = pairWiseSwap(start); // NOTE THIS CHANGE cout << "\nLinked list after calling" << "pairWiseSwap() "; printList(start); return 0; } // This code is contributed by Manoj N |
C
/* This program swaps the nodes of linked list rather than swapping the field from the nodes. Imagine a case where a node contains many fields, there will be plenty of unnecessary swap calls. */ #include <stdbool.h> #include <stdio.h> #include <stdlib.h> /* A linked list node */ struct Node { int data; struct Node* next; }; /* Function to pairwise swap elements of a linked list */ void pairWiseSwap(struct Node** head) { // If linked list is empty or there is only one node in list if (*head == NULL || (*head)->next == NULL) return; // Initialize previous and current pointers struct Node* prev = *head; struct Node* curr = (*head)->next; *head = curr; // Change head before proceeding // Traverse the list while (true) { struct Node* next = curr->next; curr->next = prev; // Change next of current as previous node // If next NULL or next is the last node if (next == NULL || next->next == NULL) { prev->next = next; break; } // Change next of previous to next next prev->next = next->next; // Update previous and curr prev = next; curr = prev->next; } } /* Function to add a node at the beginning of Linked List */ void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(struct Node* node) { while (node != NULL) { printf("%d ", node->data); node = node->next; } } /* Driver program to test above function */ int main() { struct Node* start = NULL; /* The constructed linked list is: 1->2->3->4->5->6->7 */ push(&start, 7); push(&start, 6); push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); printf("\n Linked list before calling pairWiseSwap() "); printList(start); pairWiseSwap(&start); printf("\n Linked list after calling pairWiseSwap() "); printList(start); getchar(); return 0; } |
Java
// Java program to swap elements of linked list by changing links class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Function to pairwise swap elements of a linked list */ Node pairWiseSwap(Node node) { // If linked list is empty or there is only one node in list if (node == null || node.next == null) { return node; } // Initialize previous and current pointers Node prev = node; Node curr = node.next; node = curr; // Change head before proceeding // Traverse the list while (true) { Node next = curr.next; curr.next = prev; // Change next of current as previous node // If next NULL or next is the last node if (next == null || next.next == null) { prev.next = next; break; } // Change next of previous to next next prev.next = next.next; // Update previous and curr prev = next; curr = prev.next; } return node; } /* Function to print nodes in a given linked list */ void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } // Driver program to test above functions public static void main(String[] args) { /* The constructed linked list is: 1->2->3->4->5->6->7 */ LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(2); list.head.next.next = new Node(3); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(7); System.out.println("Linked list before calling pairwiseSwap() "); list.printList(head); Node st = list.pairWiseSwap(head); System.out.println(""); System.out.println("Linked list after calling pairwiseSwap() "); list.printList(st); System.out.println(""); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python3 program to swap elements of # linked list by changing links # Linked List Node class Node:
def __init__(self, data):
self.data = data self.next = None # Create and Handle list operations class LinkedList:
def __init__(self):
# Head of list self.head = None # Add data to list def addToList(self, data):
newNode = Node(data) if self.head is None: self.head = newNode return last = self.head
while last.next: last = last.next last.next = newNode # Function to print nodes # in a given linked list def __str__(self):
linkedListStr = "" temp = self.head
while temp: linkedListStr = (linkedListStr + str(temp.data) + " ") temp = temp.next
return linkedListStr # Function to pairwise swap elements # of a linked list. It returns head of # the modified list, so return value # of this node must be assigned def pairWiseSwap(self): # If list is empty or with one node if (self.head is None or self.head.next is None): return # Initialize previous and current pointers prevNode = self.head currNode = self.head.next # Change head node self.head = currNode # Traverse the list while True: nextNode = currNode.next
# Change next of current # node to previous node currNode.next = prevNode # If next node is the last node if nextNode.next is None: prevNode.next = nextNode break # Change next of previous to # next of next prevNode.next = nextNode.next # Update previous and current nodes prevNode = nextNode currNode = prevNode.next # Driver Code linkedList = LinkedList() linkedList.addToList(1) linkedList.addToList(2) linkedList.addToList(3) linkedList.addToList(4) linkedList.addToList(5) linkedList.addToList(6) linkedList.addToList(7) print("Linked list before calling" "pairwiseSwap() ", linkedList)
linkedList.pairWiseSwap() print("Linked list after calling " "pairwiseSwap() ", linkedList) # This code is contributed by AmiyaRanjanRout |
C#
// C# program to swap elements of // linked list by changing links using System; public class LinkedList { Node head; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } /* Function to pairwise swap elements of a linked list */ Node pairWiseSwap(Node node) { // If linked list is empty or there // is only one node in list if (node == null || node.next == null) { return node; } // Initialize previous and current pointers Node prev = node; Node curr = node.next; // Change head before proceeeding node = curr; // Traverse the list while (true) { Node next = curr.next; // Change next of current as previous node curr.next = prev; // If next NULL or next is the last node if (next == null || next.next == null) { prev.next = next; break; } // Change next of previous to next of next prev.next = next.next; // Update previous and curr prev = next; curr = prev.next; } return node; } /* Function to print nodes in a given linked list */ void printList(Node node) { while (node != null) { Console.Write(node.data + " "); node = node.next; } } // Driver code public static void Main(String[] args) { /* The constructed linked list is: 1->2->3->4->5->6->7 */ LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(2); list.head.next.next = new Node(3); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(7); Console.WriteLine("Linked list before calling pairwiseSwap() "); list.printList(list.head); Node st = list.pairWiseSwap(list.head); Console.WriteLine(""); Console.WriteLine("Linked list after calling pairwiseSwap() "); list.printList(st); Console.WriteLine(""); } } // This code contributed by Rajput-Ji |
Javascript
<script> // javascript program to swap elements of linked list by changing links var head; class Node { constructor(val) { this.data = val; this.next = null; } }
/* Function to pairwise swap elements of a linked list */ function pairWiseSwap(node) { // If linked list is empty or there is only one node in list if (node == null || node.next == null) { return node; } // Initialize previous and current pointers var prev = node; var curr = node.next; node = curr; // Change head before proceeding // Traverse the list while (true) { var next = curr.next; curr.next = prev; // Change next of current as previous node // If next NULL or next is the last node if (next == null || next.next == null) { prev.next = next; break; } // Change next of previous to next next prev.next = next.next; // Update previous and curr prev = next; curr = prev.next; } return node; } /* Function to print nodes in a given linked list */ function printList(node) { while (node != null) { document.write(node.data + " "); node = node.next; } } // Driver program to test above functions
/* * The constructed linked list is: 1->2->3->4->5->6->7 */ head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next.next = new Node(7); document.write("Linked list before calling pairwiseSwap() "); printList(head); var st = pairWiseSwap(head); document.write("<br/>"); document.write("Linked list after calling pairwiseSwap() "); printList(st); document.write(""); // This code contributed by aashish2995 </script> |
Output:
Linked list before calling pairWiseSwap() 1 2 3 4 5 6 7 Linked list after calling pairWiseSwap() 2 1 4 3 6 5 7Time Complexity: The time complexity of the above program is O(n) where n is the number of nodes in a given linked list. The while loop does a traversal of the given linked list.
Following is the recursive implementation of the same approach. We change the first two nodes and recur for the remaining list. Thanks to geek and omer salem for suggesting this method.
C++
/* This program swaps the nodes of linked list rather than swapping the field from the nodes. Imagine a case where a node contains many fields, there will be plenty of unnecessary swap calls. */ #include <bits/stdc++.h> using namespace std; /* A linked list node */ class node { public: int data; node* next; }; /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ node* pairWiseSwap(node* head) { // Base Case: The list is empty or has only one node if (head == NULL || head->next == NULL) return head; // Store head of list after two nodes node* remaining = head->next->next; // Change head node* newhead = head->next; // Change next of second node head->next->next = head; // Recur for remaining list and change next of head head->next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to add a node at the beginning of Linked List */ void push(node** head_ref, int new_data) { /* allocate node */ node* new_node = new node(); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } /* Driver program to test above function */ int main() { node* start = NULL; /* The constructed linked list is: 1->2->3->4->5->6->7 */ push(&start, 7); push(&start, 6); push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); cout << "Linked list before calling pairWiseSwap() "; printList(start); start = pairWiseSwap(start); // NOTE THIS CHANGE cout << "\nLinked list after calling pairWiseSwap() "; printList(start); return 0; } // This is code is contributed by rathbhupendra |
C
/* This program swaps the nodes of linked list rather than swapping the field from the nodes. Imagine a case where a node contains many fields, there will be plenty of unnecessary swap calls. */ #include <stdbool.h> #include <stdio.h> #include <stdlib.h> /* A linked list node */ struct node { int data; struct node* next; }; /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ struct node* pairWiseSwap(struct node* head) { // Base Case: The list is empty or has only one node if (head == NULL || head->next == NULL) return head; // Store head of list after two nodes struct node* remaining = head->next->next; // Change head struct node* newhead = head->next; // Change next of second node head->next->next = head; // Recur for remaining list and change next of head head->next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to add a node at the beginning of Linked List */ void push(struct node** head_ref, int new_data) { /* allocate node */ struct node* new_node = (struct node*)malloc(sizeof(struct node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(struct node* node) { while (node != NULL) { printf("%d ", node->data); node = node->next; } } /* Driver program to test above function */ int main() { struct node* start = NULL; /* The constructed linked list is: 1->2->3->4->5->6->7 */ push(&start, 7); push(&start, 6); push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); printf("\n Linked list before calling pairWiseSwap() "); printList(start); start = pairWiseSwap(start); // NOTE THIS CHANGE printf("\n Linked list after calling pairWiseSwap() "); printList(start); return 0; } |
Java
// Java program to swap elements of linked list by changing links class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ Node pairWiseSwap(Node node) { // Base Case: The list is empty or has only one node if (node == null || node.next == null) { return node; } // Store head of list after two nodes Node remaining = node.next.next; // Change head Node newhead = node.next; // Change next of second node node.next.next = node; // Recur for remaining list and change next of head node.next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to print nodes in a given linked list */ void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } // Driver program to test above functions public static void main(String[] args) { /* The constructed linked list is: 1->2->3->4->5->6->7 */ LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(2); list.head.next.next = new Node(3); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(7); System.out.println("Linked list before calling pairwiseSwap() "); list.printList(head); head = list.pairWiseSwap(head); System.out.println(""); System.out.println("Linked list after calling pairwiseSwap() "); list.printList(head); System.out.println(""); } } |
Python3
# Python3 program to pairwise swap # linked list using recursive method # Linked List Node class Node:
def __init__(self, data):
self.data = data self.next = None # Create and Handle list operations class LinkedList:
def __init__(self):
# Head of list self.head = None # Add data to list def addToList(self, data):
newNode = Node(data)
if self.head is None: self.head = newNode return last = self.head
while last.next: last = last.next last.next = newNode # Function to print nodes in # a given linked list def __str__(self):
linkedListStr = "" temp = self.head
while temp: linkedListStr = (linkedListStr + str(temp.data) + " ") temp = temp.next return linkedListStr # Function to pairwise swap elements of # a linked list.It returns head of the # modified list, so return value # of this node must be assigned def pairWiseSwap(self, node): # If list is empty or with one node if node is None or node.next is None: return node # Store head of list after 2 nodes remaining = node.next.next # Change head newHead = node.next # Change next to second node node.next.next = node # Recur for remaining list and # change next of head node.next = self.pairWiseSwap(remaining) # Return new head of modified list return newHead # Driver Code linkedList = LinkedList() linkedList.addToList(1) linkedList.addToList(2) linkedList.addToList(3) linkedList.addToList(4) linkedList.addToList(5) linkedList.addToList(6) linkedList.addToList(7) print("Linked list before calling " "pairwiseSwap() ", linkedList)
linkedList.head = linkedList.pairWiseSwap( linkedList.head) print("Linked list after calling " "pairwiseSwap() ", linkedList) # This code is contributed by AmiyaRanjanRout |
C#
// C# program to swap elements // of linked list by changing links using System; public class LinkedList { Node head; class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ Node pairWiseSwap(Node node) { // Base Case: The list is empty // or has only one node if (node == null || node.next == null) { return node; } // Store head of list after two nodes Node remaining = node.next.next; // Change head Node newhead = node.next; // Change next of second node node.next.next = node; // Recur for remaining list // and change next of head node.next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to print nodes in a given linked list */ void printList(Node node) { while (node != null) { Console.Write(node.data + " "); node = node.next; } } // Driver program to test above functions public static void Main() { /* The constructed linked list is: 1->2->3->4->5->6->7 */ LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(2); list.head.next.next = new Node(3); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(7); Console.WriteLine("Linked list before calling pairwiseSwap() "); list.printList(list.head); list.head = list.pairWiseSwap(list.head); Console.WriteLine(""); Console.WriteLine("Linked list after calling pairwiseSwap() "); list.printList(list.head); Console.WriteLine(""); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // javascript program to swap elements of linked list by changing links var head; class Node { constructor(val) { this.data = val; this.next = null; } } /* * Function to pairwise swap elements of a linked It returns head of the * modified list, so return value of this node must be assigned */ function pairWiseSwap(node) { // Base Case: The list is empty or has only one node if (node == null || node.next == null) { return node; } // Store head of list after two nodes var remaining = node.next.next; // Change head var newhead = node.next; // Change next of second node node.next.next = node; // Recur for remaining list and change next of head node.next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to print nodes in a given linked list */ function printList(node) { while (node != null) { document.write(node.data + " "); node = node.next; } } // Driver program to test above functions
/* * The constructed linked list is: 1->2->3->4->5->6->7 */ head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next.next = new Node(7); document.write("Linked list before calling pairwiseSwap() "); printList(head); head = pairWiseSwap(head); document.write("<br/>"); document.write("Linked list after calling pairwiseSwap() "); printList(head); document.write(""); // This code contributed by umadevi9616 </script> |
Output:
Linked list before calling pairWiseSwap() 1 2 3 4 5 6 7 Linked list after calling pairWiseSwap() 2 1 4 3 6 5 7Pairwise swap adjacent nodes of a linked list by changing pointers | Set 2
This article is contributed by Gautam Kumar. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Article Tags :
Linked List
Linked Lists
Practice Tags :
Linked List
Read Full Article
Program to swap nodes in a singly linked list without swapping data
Explanation
In this program, we need to swap given two nodes in the singly linked list without swapping data.
One of the approaches to accomplish this task is to swap the previous nodes of the given two nodes and then, swap the next nodes of two nodes.
Algorithm
- Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list.
- Create another class SwapNodes which has two attributes: head and tail.
- addNode() will add a new node to the list:
- Create a new node.
- It first checks, whether the head is equal to null which means the list is empty.
- If the list is empty, both head and tail will point to a newly added node.
- If the list is not empty, the new node will be added to end of the list such that tail's next will point to a newly added node. This new node will become the new tail of the list.
- swap() will swap the given two nodes present in the list:
- Let n1 and n2 be the values need to be swapped.
- If the list is empty then, return from the function.
- If n1 and n2 are equal then, there will be no change in the list.
- If the list is not empty then, search for n1 by traversing through the list such that prevNode1 which will point to node previous to node1 and node 1 will point to the node having value n1.
- Similarly, search for n2 by traversing through the list such that prevNode2 which will point to node previous to node2 and node 2 will point to the node having value n2.
- If prevNode1 points to head then, node2 will become head of the list. Similarly, if prevNode2 points to head then, node1 will become head of the list.
- If prevNode1 or prevNode2 is not pointing to head then, swap the nodes such that prevNode1 will become the previous node of node2 and prevNode2 will become the previous node of node1.
- Now, swap next nodes of node1 and node2.
- display() will display the nodes present in the list:
- Define a node current which will initially point to the head of the list.
- Traverse through the list till current points to null.
- Display each node by making current to point to node next to it in each iteration.
Solution
Python
Output:
Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2
C
Output:
Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2
JAVA
Output:
Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2
C#
Output:
Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2
PHP
Output:
Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2