Pairwise swap nodes of linked list - Data Structure

Problem Statement: Given a singly linked list. Your task is to swap all the elements pairwise.

Examples:

Example 1:
Input: Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL 

Output: 2->1->4->3->6->5->NULL

Explanation: While traversing the linked list every time 
we encounter a pair we have to swap them. i.e pair(1,2) 
is swapped with (2,1), pair(3,4) is swapped with (4,3), 
and so on.

Example 2:
Input: Linked list: 1->2->3->4->5->NULL 

Output: 2->1->4->3->5->NULL

Explanation: While traversing the linked list every time 
we encounter a pair we have to swap them. Here the last 
element 5 at the end of the list does not have any pair 
to swap it with, so it remains unchanged.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Iterative method

Approach: Start the traversal from the head node of the linked list till the end of the linked list. While traversing swap data of each and every node with its next node’s data. until the appearance of null. i.e End of the list.

Let’s understand it with the help of some diagrams.

1st iteration:

2nd iteration:

3rd iteration:

4th iteration:

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

class Node {
  public:
    int data;
  Node * next;
};

/* Function to pairwise swap elements */
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;
  }
}

void push(Node ** head_ref, int new_data) {
  
  Node * new_node = new Node();
  
new_node -> data = new_data;

  new_node -> next = ( * head_ref);

  ( * head_ref) = new_node;
}

void printList(Node * node) {
  while (node != NULL) {
    cout << node -> data << " ";
    node = node -> next;
  }
}

int main() {
  Node * start = NULL;

  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;
}

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)

Reason: Linked list traversal takes linear time complexity

Space Complexity: O(1)

Java Code

class TUF {
  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;
    }
  }

  public void push(int new_data) {

    Node new_node = new Node(new_data);
    new_node.next = head;
    head = new_node;
  }

  void printList() {
    Node temp = head;
    while (temp != null) {
      System.out.print(temp.data + " ");
      temp = temp.next;
    }
    System.out.println();
  }

  public static void main(String args[]) {
    TUF llist = new TUF();
    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();
  }
}

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)

Reason: Linked list traversal takes linear time complexity

Space Complexity: O(1)

Solution 2: Recursive method

Approach: 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.

The base case will be the end of the list and the edge case will be the list with a size less than 2.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

class Node {
  public:
    int data;
  Node * next;
};

/* Function to pairwise swap elements */
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);
  }
}

void push(Node ** head_ref, int new_data) {

  Node * new_node = new Node();
  new_node -> data = new_data;
  new_node -> next = ( * head_ref);
  ( * head_ref) = new_node;
}

void printList(Node * node) {
  while (node != NULL) {
    cout << node -> data << " ";
    node = node -> next;
  }
}

int main() {
  Node * start = NULL;

  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;
}

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)

Reason: Linked list traversal takes linear time complexity

Space Complexity: O(1)

Java Code

class TUF {
  Node head; // head of list

  /* Linked list Node*/
  class Node {
    int data;
    Node next;
    Node(int d) {
      data = d;
      next = null;
    }
  }

  public 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);
      int t = head.data;
      head.data = head.next.data;
      head.next.data = t;

      /* Call pairWiseSwap() for rest of the list */
      pairWiseSwap(head.next.next);
    }
  }

  public void push(int new_data) {
    Node new_node = new Node(new_data);
    new_node.next = head;
    head = new_node;
  }

  void printList() {
    Node temp = head;
    while (temp != null) {
      System.out.print(temp.data + " ");
      temp = temp.next;
    }
    System.out.println();
  }

  public static void main(String args[]) {
    TUF llist = new TUF();
    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(llist.head);

    System.out.println("Linked List after calling pairWiseSwap() ");
    llist.printList();
  }
}

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)

Reason: Linked list traversal takes linear time complexity

Space Complexity: O(1)

Special thanks to Abhishek Yadav for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article