Pairwise swap adjacent nodes of a linked list by changing pointers | Set 2
Given a singly linked list, write a function to swap elements pairwise.
Input : 1->2->3->4->5->6->7 Output : 2->1->4->3->6->5->7, Input : 1->2->3->4->5->6 Output : 2->1->4->3->6->5
A solution has been discussed set 1. Here a simpler solution is discussed. We explicitly change pointers of first two nodes, then fix remaining nodes.
Implementation:
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 */ struct Node { int data; struct Node *next; }; /* Function to pairwise swap elements of a linked list */ 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; // Fix the head and its next explicitly to // avoid many if else in while loop Node *curr = head->next->next; Node *prev = head; head = head->next; head->next = prev; // Fix remaining nodes while (curr != NULL && curr->next != NULL) { prev->next = curr->next; prev = curr; Node *next = curr->next->next; curr->next->next = curr; curr = next; } prev->next = curr; return head; } /* Function to add a node at the beginning of Linked List */ void push( struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*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); printf ( "\n Linked list after calling pairWiseSwap() " ); printList(start); return 0; } |
Java
/* 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. */ class GfG { /* A linked list node */ static class Node { int data; Node next; } static Node head = null ; /* Function to pairwise swap elements of a linked list */ static 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; // Fix the head and its next explicitly to // avoid many if else in while loop Node curr = head.next.next; Node prev = head; head = head.next; head.next = prev; // Fix remaining nodes while (curr != null && curr.next != null ) { prev.next = curr.next; prev = curr; Node next = curr.next.next; curr.next.next = curr; curr = next; } prev.next = curr; return head; } /* Function to add a node at the beginning of Linked List */ static void push( int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head); (head) = new_node; } /* Function to print nodes in a given linked list */ static void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } } /* Driver code */ public static void main(String[] args) { //Node head = null; /* The constructed linked list is: 1->2->3->4->5->6->7 */ push( 7 ); push( 6 ); push( 5 ); push( 4 ); push( 3 ); push( 2 ); push( 1 ); System.out.print( "\n Linked list before calling pairWiseSwap() " ); printList(head); Node start = pairWiseSwap(head); System.out.print( "\n Linked list after calling pairWiseSwap() " ); printList(start); } } // This code is contributed by Prerna Saini. |
Python3
# 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. # A linked list node class Node: def __init__( self , data): self .data = data self . next = None # Function to pairwise swap elements of a # linked list def pairWiseSwap(head): # If linked list is empty or there is only # one node in list if (head = = None or head. next = = None ): return head # Fix the head and its next explicitly to # avoid many if else in while loop curr = head. next . next prev = head head = head. next head. next = prev # Fix remaining nodes while (curr ! = None and curr. next ! = None ): prev. next = curr. next prev = curr next = curr. next . next curr. next . next = curr curr = next prev. next = curr return head # Function to add a node at the beginning # of Linked List def push(head_ref, new_data): new_node = Node(new_data) new_node. next = (head_ref) (head_ref) = new_node return head_ref # Function to print nodes in a # given linked list def printList(node): while (node ! = None ): print (node.data, end = ' ' ) node = node. next # Driver Code if __name__ = = '__main__' : start = None # The constructed linked list is: # 1.2.3.4.5.6.7 start = push(start, 7 ) start = push(start, 6 ) start = push(start, 5 ) start = push(start, 4 ) start = push(start, 3 ) start = push(start, 2 ) start = push(start, 1 ) print ( "\nLinked list before " "calling pairWiseSwap() " , end = '') printList(start) start = pairWiseSwap(start) print ( "\nLinked list after calling " "pairWiseSwap() " , end = '') printList(start) # This code is contributed by rutvik_56 |
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. */ using System; class GfG { /* A linked list node */ class Node { public int data; public Node next; } static Node head = null ; /* Function to pairwise swap elements of a linked list */ static 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; // Fix the head and its next explicitly to // avoid many if else in while loop Node curr = head.next.next; Node prev = head; head = head.next; head.next = prev; // Fix remaining nodes while (curr != null && curr.next != null ) { prev.next = curr.next; prev = curr; Node next = curr.next.next; curr.next.next = curr; curr = next; } prev.next = curr; return head; } /* Function to add a node at the beginning of Linked List */ static void push( int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head); (head) = new_node; } /* Function to print nodes in a given linked list */ static void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } } /* Driver code */ public static void Main() { //Node head = null; /* The constructed linked list is: 1->2->3->4->5->6->7 */ push( 7); push( 6); push( 5); push( 4); push(3); push( 2); push( 1); Console.Write( "\n Linked list before" + "calling pairWiseSwap() " ); printList(head); Node start = pairWiseSwap(head); Console.Write( "\n Linked list after" + "calling pairWiseSwap() " ); printList(start); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> /* 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. */ /* A linked list node */ class Node { constructor() { this .data = 0; this .next = null ; } } var head = null ; /* Function to pairwise swap elements of a linked list */ function pairWiseSwap(head) { // If linked list is empty or there // is only one node in list if (head == null || head.next == null ) return head; // Fix the head and its next explicitly to // avoid many if else in while loop var curr = head.next.next; var prev = head; head = head.next; head.next = prev; // Fix remaining nodes while (curr != null && curr.next != null ) { prev.next = curr.next; prev = curr; var next = curr.next.next; curr.next.next = curr; curr = next; } prev.next = curr; return head; } /* Function to add a node at the beginning of Linked List */ function push(new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = (head); (head) = new_node; } /* Function to print nodes in a given linked list */ function printList(node) { while (node != null ) { document.write(node.data + " " ); node = node.next; } } /* Driver code */ /* The constructed linked list is: 1->2->3->4->5->6->7 */ push( 7); push( 6); push( 5); push( 4); push(3); push( 2); push( 1); document.write( "Linked list before" + "calling pairWiseSwap() " ); printList(head); var start = pairWiseSwap(head); document.write( "<br> Linked list after" + "calling pairWiseSwap() " ); printList(start); </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 7
Time complexity : O(n)
Auxiliary Space: O(1)
Another approach: The approach here is to use the double pointers so that we need not update the head pointer during swap separately.
Implementation:
C++
#include <bits/stdc++.h> using namespace std; // A nexted list node struct Node { int data; struct Node* next; }; /* Function to insert a node at the beginning */ void push( struct Node** head_ref, int new_data) { struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Utility function to print a singly linked list */ void printList( struct Node* head) { struct Node* temp = head; while (temp != NULL) { cout << temp->data << " " ; temp = temp->next; } cout << endl; } // Function to swap adjacent nodes void swapPairs( struct Node** head) { // Loop until we reach the last node while (*head && (*head)->next) { struct Node* one = *head; struct Node* two = one->next->next; *head = one->next; one->next->next = one; one->next = two; head = &one->next; } } // Driver program to test above functions int main() { struct Node* head = NULL; push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << ( "Actual List:\n" ); printList(head); swapPairs(&head); cout << ( "ModifiedLinked List:\n" ); printList(head); } // This code is contributed by garg28harsh. |
C
#include <stdio.h> #include <stdlib.h> // A nexted list node struct Node { int data; struct Node *next; }; /* Function to insert a node at the beginning */ void push( struct Node ** head_ref, int new_data) { struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Utility function to print a singly linked list */ void printList( struct Node *head) { struct Node *temp = head; while (temp != NULL) { printf ( "%d " , temp->data); temp = temp->next; } printf ( "\n" ); } // Function to swap adjacent nodes void swapPairs( struct Node **head) { //Loop until we reach the last node while (*head && (*head)->next) { struct Node *one = *head; struct Node *two = one->next->next; *head = one->next; one->next->next = one; one->next = two; head = &one->next; } } // Driver program to test above functions int main() { struct Node *head = NULL; push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); printf ( "Actual List:\n" ); printList(head); swapPairs(&head); printf ( "ModifiedLinked List:\n" ); printList(head); getchar (); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.Scanner; class Node { int data; Node next; Node( int d) { data = d; next = null ; } } class LinkedList { Node head; // Function to insert a node at the beginning void push( int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Utility function to print a singly linked list void printList() { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } System.out.println(); } void swapPairs(Node head) { Node current = head; // Loop until we reach the last node while (current != null && current.next != null ) { int temp = current.data; current.data = current.next.data; current.next.data = temp; current = current.next.next; } } public static void main(String[] args) { LinkedList list = new LinkedList(); list.push( 6 ); list.push( 5 ); list.push( 4 ); list.push( 3 ); list.push( 2 ); list.push( 1 ); System.out.println( "Actual List:" ); list.printList(); list.swapPairs(list.head); System.out.println( "Modified Linked List:" ); list.printList(); } } |
C#
using System; class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } class LinkedList { public Node head; // Function to insert a node at the beginning public void push( int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Utility function to print a singly linked list public void printList() { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } Console.WriteLine(); } public void swapPairs(Node head) { Node current = head; // Loop until we reach the last node while (current != null && current.next != null ) { int temp = current.data; current.data = current.next.data; current.next.data = temp; current = current.next.next; } } public static void Main( string [] args) { LinkedList list = new LinkedList(); list.push(6); list.push(5); list.push(4); list.push(3); list.push(2); list.push(1); Console.WriteLine( "Actual List:" ); list.printList(); list.swapPairs(list.head); Console.WriteLine( "Modified Linked List:" ); list.printList(); } } // this code is contributed by devendra |
Javascript
class Node { constructor(data) { this .data = data; this .next = null ; } } // Function to insert a node at the beginning function push(list, newData) { let newNode = new Node(newData); newNode.next = list.head; list.head = newNode; } // Utility function to print a singly linked list function printList(head) { let temp = head; while (temp !== null ) { console.log(temp.data); temp = temp.next; } } // Function to swap adjacent nodes function swapPairs(list) { let head = list.head; let dummy = new Node( null ); dummy.next = head; let prev = dummy; while (head && head.next) { let one = head; let two = one.next.next; prev.next = one.next; one.next.next = one; one.next = two; prev = one; head = one.next; } list.head = dummy.next; } let list = {head: null }; push(list, 6); push(list, 5); push(list, 4); push(list, 3); push(list, 2); push(list, 1); console.log( "Actual List:" ); printList(list.head); swapPairs(list); console.log( "Modified Linked List:" ); printList(list.head); |
Python3
class Node: def __init__( self , data): self .data = data self . next = None class LinkedList: def __init__( self ): self .head = None # Function to insert a 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 a singly linked list def printList( self ): temp = self .head while temp: print (temp.data, end = " " ) temp = temp. next print () def swapPairs( self , head): current = head # Loop until we reach the last node while current and current. next : temp = current.data current.data = current. next .data current. next .data = temp current = current. next . next # Test linked_list = LinkedList() linked_list.push( 6 ) linked_list.push( 5 ) linked_list.push( 4 ) linked_list.push( 3 ) linked_list.push( 2 ) linked_list.push( 1 ) print ( "Actual List:" ) linked_list.printList() linked_list.swapPairs(linked_list.head) print ( "Modified Linked List:" ) linked_list.printList() # this code is contributed by writer |
Output
Actual List: 1 2 3 4 5 6 ModifiedLinked List: 2 1 4 3 6 5
Time complexity: O(n), where n is the number of nodes in the linked list. This is because the code iterates through each node in the linked list once and performs a constant amount of operations on each node.
Auxiliary Space: O(1)