Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Frequently Asked Questions
4.1.
What are prev, current, and next pointing to when we pairwise swap the elements of the Linked List?
4.2.
What is the time complexity for the approach we have used to pairwise swap the elements of the Linked List?
4.3.
Is there any other method to solve this problem?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

Pairwise Swap Elements of a Given Linked List by Changing Links

Author Nishant Rana
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM
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. 

Recommended Topic, Floyds Algorithm

Problem Statement

You are given a LinkedList and you need to pairwise swap the elements of the LinkedList by changing their links.

Let us see a few examples:

Input 1:

1 -> 2 -> 3 -> 4 -> 5

Output 1:

2 -> 1 -> 4 -> 3 -> 5

 

Input 2:

1 -> 2 -> 3 -> 4

Output 2:

2 -> 1 -> 4 -> 3

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach


We will maintain the following 3 pointers:

  1. current: We will use this pointer to traverse the LinkedList.
  2. prev: This will point to the previous pointer of the current node.
  3. nextOfCur: This will point to the next pointer of the current node.

At any node we will do the following:

  1. First, we will set the next of current to be prev i.e. current.next = prev.
  2. Then, we will set the next of prev to be the next of nextOfCur i.e. prev.next = nextOfCur.next.
  3. Then we will update the prev and current pointers.

 

Refer to the below implementation of the above approach.

public Node pairWiseSwap(Node head){

    /*
      If the linked list is 
      empty or there is only 
      one node in list
    */
    if (head == null || head.next == null) {
        return head;
    }

    // Initialize the previous and current pointers
    Node prev = head;
    Node current = head.next;

    head = current; 

    // Traversing the list
    while (true) {
        Node nextOfCur = current.next;
        
        /* 
          Updating the next
          of the current 
          pointer to be prev.
        */
        current.next = prev; 

        // If next is NULL or next is the last node
        if (nextOfCur  == null || nextOfCur.next == null) {
            prev.next = nextOfCur;
            break;
        }

        // Change next of previous to next next
        prev.next = nextOfCur.next;

        // Update the previous and current
        prev = nextOfCur;
        current = prev.next;
    }
    return head;

}
 

Time Complexity: The time complexity for the above approach to pairwise swap the elements of the Linked List is O(N) (where ‘N’ is the number of nodes in the Linked List) because we are just iterating the Linked List once.

Space Complexity: The space complexity of the above approach to pairwise swap the elements of the Linked List is O(1) because we are using the constant auxiliary space.

 

Frequently Asked Questions

What are prev, current, and next pointing to when we pairwise swap the elements of the Linked List?

current: We will use this pointer to traverse the LinkedList. 
prev: This will point to the previous pointer of the current node.  
nextOfCur: This will point to the next pointer of the current node.

What is the time complexity for the approach we have used to pairwise swap the elements of the Linked List?

The time complexity for the approach to pairwise swap the elements of the Linked List is O(N) (where N is the number of nodes in the Linked List) because we are just iterating the Linked List once.

Is there any other method to solve this problem?

Yes, we can also solve this question by just swapping the data of adjacent nodes instead of changing the links of the nodes.

 

Conclusion

In this blog, we have covered the following things:

  1. We first discussed the approach to pairwise swap the elements of the Linked List.
  2. Then we implemented the approach we discussed.

If you want to learn more about Linked List and want to practice some questions which require you to take your basic knowledge on Linked List a notch higher, then you can visit our Guided Path for Linked List. To practice this problem, you can visit Practice Problem.

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.

Cheers! 

Previous article
Pairwise Swap Adjacent Nodes of a Linked List by Changing Pointers
Next article
Add Two Numbers Represented by the Linked Lists | Part-1
Live masterclass