Table of contents
1.
Introduction
2.
Problem Statement 
3.
Recursive Approach
3.1.
Algorithm
3.2.
Pseudo Code
3.3.
Implementation in C++
3.4.
Implementation in Java
3.5.
Complexity Analysis
4.
Frequently Asked Questions 
4.1.
What exactly is a singly linked list?
4.2.
How long does it take to traverse a singly linked list asymptotically?
4.3.
In which header list will you find the null pointer in the last node?
4.4.
Is recursion more memory intensive?
4.5.
How much more memory does a recursive stack take than a basic integer memory allocation?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Swap Nodes in Pairs

Author Alisha Chhabra
3 upvotes
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Linked List

Introduction

A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations. Linked Lists are one of the most fundamental and important data structures having a wide range of applications. Linked Lists are also important from the perspective of interviews as well. 

Problem Statement 

The challenge for today is to swap nodes in pairs of the given singly linked list. 

The Problem says:

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves can be changed.)

Example 1:

Linked List

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Example 2:-

Linked List

Input: head = [1, 2, 3, 4, 5]

Output: [2,1,4,3,5]

Example 3:-

Linked List

Input: head=[1]

Output: [1]

Example 4:-

Input: [ ]

Output: [ ]

 

Before proceeding to the solution, it is advised that you attempt the given problem on your own.

Let’s discuss the idea about implementing the code:

If we were allowed to modify the values of the nodes, the problem would be so simple. However, in this case, we must update the link, i.e., the reference of the nodes. 

The below diagram demonstrates the idea:-

Illustration IMage

In the above diagram, Pair-one links have been changed. Node-2 is linked to Node-1, which is linked to Node-4 and so forth for Pair-two. 

The challenge now is how to replicate this. Got any approaches?
 

Cool, let us discuss the approach now:-

Recursive Approach

The idea is we'll swap the current pair of nodes and then move on to the next ones. By swapping means, updating the reference of the nodes to the respective nodes, then for further connection of the nodes, we can manage to connect to the swapped result for the entire subsequent linked list via recursive calls.

Let's look at the recursive rules now:

Base Case: The input linked list is either empty or contains only one node, the head.

We need to cover two scenarios for the base case because as long as the number of nodes in the input list is less than two, we don't need to swap but return the head directly.

Recursive Rule:-

1) Swap all pairs in the following sub-list.

2) Swap the current pair and join them correctly with the result retrieved from the following list via recursive call.

Let us discuss the algorithm for the idea we’ve discussed above:-

Algorithm

Step 1:- Make a function swapPairs( ) which takes one parameter, i.e., the Head of the linked list. 

Step 1.2:- Check if the LinkedList is empty or has one node; if yes, return head.

Step 1.3:- Otherwise, create a new Node new_head which will always refer to the second node in a pair.

Step 1.4:- Before updating the link of the second node in a pair, we need to take care of the third node. 

For example:- 1->2->3->4

Here, 1 is the head, 2 is the new_head, now if we try to change the link of node-2 from node-3 to node-1, we’ll not be able to access the following list. 

We need to create one new Node that will point to the adjacent node of the current pair, i.e., the Node-3 in the below example.

Illustration IMage

         Step 1.5:- Update the link of the new_head. 

new_head->next = head;

 

So far, we’ve changed the link of the second node in a pair. Now we need to splice the Node-1 to the retrieved swapped result from the recursive call. 

Illustration IMage

Step 1.6:- Now, make a recursive call. And then pass the third node as an argument. 

We need to skip the current pair since we will swap them within the current function call. Thus, we will pass the third node head into the next recursive call and retrieve the swapped result. 

After getting the sub-problem result, we will swap the current pair and splice it to the front.

          Step 1.7:- Return new_head.

 

Now, let us analyze the pseudo-code for Swap Nodes in Pairs:-

Pseudo Code

ListNode* swapPairs(ListNode* head)

        if (head == nullptr || head->next == nullptr) 
            return head
        ListNode* new_head = head->next
        ListNode* third = head->next->next
        new_head->next = head
        head->next = swapPairs(third)

  return new_head

Let’s move on to the Implementation of the problem:

Implementation in C++

// C++ program to swap Nodes in pairs using a recursive approach

#include <bits/stdc++.h>
using namespace std;

// Definition for singly-linked list
struct ListNode
{
    int value;
    ListNode* next;
    ListNode(int x)
    {
        value = x;
        next = NULL;
    }
};
// function to print the LinkedList
void print(ListNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return ;
}
// Function definition for swapping the nodes
ListNode* swapPairs(ListNode* head) {
    
        // Check whether the list is empty or has one node
        // If yes, then return head
        if (head == nullptr || head->next == nullptr) return head;
        
        // If the list has more than 1 node, then initialize a new node
        // which will always point to the second node of a pair
        ListNode* new_head = head->next;
        
        // initialize a new node for pointing to the adjacent node of a pair
        ListNode* third = head->next->next;
        
        // Update the link 
        // for example 1->2->3->null
        // Result = 2->1   3->null
        new_head->next = head;
        
        // Update the head link
        // Result = 2->1->{retireved value} via recursive call
        head->next = swapPairs(third);
        
        // Finally, return the new list
        return new_head;
    }
    // main function
int main()
{
    // Construct the below LinkedList
    /* 
      1->2->3->4->null
    */
    ListNode* head = new ListNode(1);
    // 1->2
    head->next = new ListNode(2);
    // 1->2->3
    head->next->next = new ListNode(3);
    // 1->2->3->4
    head->next->next->next = new ListNode(4);
    
    cout<<"Original linked list : "<<endl;
    print(head);
    cout<<"Updated list after swapping :"<<endl;
    print(swapPairs(head));
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Output

Original linked list : 
1 2 3 4 
Updated list after swapping :
2 1 4 3 

Implementation in Java

// Java program to swap Nodes in pairs using a recursive approach

import java.io.*;
import java.util.*;
public class ListNode
{
    // Definition for singly-linked list
    int value;
    ListNode next;
    ListNode(int x)
    {
        value = x;
        next = null;
    }
    // Utility function to print the LinkedList
    public static void print(ListNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }
    
    // Function definition for swapping the nodes
    public static ListNode swapPairs(ListNode head) {
        // Check whether the list is empty or has one node
        // If yes, then return head
        if(head==null || head.next==null){
            return head;
        }
        
        // If the list has more than 1 node, then initialize a new node
        // which will always point to the second node of a pair
        ListNode new_head = head.next;
        // initialize a new node for pointing to the adjacent node of a pair
        ListNode third = head.next.next;
        // Update the link 
        // for example 1->2->3->null
        // Result = 2->1   3->null
        new_head.next = head;
        // Update the head link
        // Result = 2->1->{retireved value} via recursive call
        head.next = swapPairs(third);
        // Finally return the new list
        return new_head;
        
    }
    public static void main(String args[])
    {
        // Construct the below LinkedList
        /* 
          1->2->3->4->null
        */
        ListNode head = new ListNode(1);
        // 1->2
        head.next = new ListNode(2);
        // 1->2->3
        head.next.next = new ListNode(3);
        // 1->2->3->4
        head.next.next.next = new ListNode(4);
        System.out.println("Original Linked List: ");
        print(head);
        System.out.println("\nUpdated List after swapping: ");
        print(swapPairs(head));
    }
}
You can also try this code with Online Java Compiler
Run Code

Output

Original Linked list : 
1 2 3 4 
Updated list after swapping :
2 1 4 3 
animation

Complexity Analysis

Time Complexity to Swap Nodes in Pairs:- O(N), as we solely do a single pass on the LinkedList.

Space Complexity to Swap Nodes in Pairs:- O(N), as the recursion generates stack frames for each call in the memory.

Frequently Asked Questions 

What exactly is a singly linked list?

A single linked list is a form of a unidirectional linked list, meaning that it can only be traversed in one way, from head to tail node.

How long does it take to traverse a singly linked list asymptotically?

This corresponds to a Ω(n) lower constraint on the running time of traversal in a single linked list in conventional models such as RAM.

In which header list will you find the null pointer in the last node?

The last node in the grounded header list has a null pointer.

Is recursion more memory intensive?

Recursion consumes more memory, but it can also be more legible and understandable. Although using loops improves efficiency, recursion might sometimes be more beneficial to the programmer (and his performance).

How much more memory does a recursive stack take than a basic integer memory allocation?

Recursion will repeatedly call the same function until a parameter in the function is met, and the final call in the recursive branch begins to return. Before the return, all function calls are piled on top of one another, occupying (Number of recursive calls) * (memory required by one function call) memory space

Conclusion

To sum up the session, we used a recursive method to solve the problem of Swap Nodes in Pairs. This problem can be addressed in an iterative manner, similar to the method described above. Now it's your time, Ninja, to solve the problem in your preferred language.

Make sure you execute the code on a dry run and are completely honest with each step. Trust me; this will drastically be going to improve your problem-solving abilities.

Nonetheless, Ninja, don't stop here; keep looking for more excellent articles to help you on your coding path.

Check out this problem - Reverse Nodes In K Group

Furthermore, we provide a wide range of top-tier courses taught by highly regarded faculty.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Live masterclass