Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution
3.1.
Implementation in C++ 
4.
Recursive Approach
4.1.
Implementation in C++ 
5.
Frequently Asked Questions
5.1.
What is a linked list?
5.2.
What is the key difference between a singly linked list and a doubly-linked list?
5.3.
Which approach iterative or recursive is better to be considered?
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

Pairwise Swap Adjacent Nodes of a Linked List by Changing Pointers

Author GAZAL ARORA
0 upvote
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

Write a function to swap pairwise elements of a given singly Linked List.

Example:

Input : 1->3->5->7
Output : 3->1->7->5,

Input : 1->2->3->4
Output : 2->1->4->3

Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 

Solution

Recommended: Please try to solve it yourself first before moving on to the solution.

 

The idea is simple:

  1. We will swap the nodes themselves instead of swapping the node values only.
  2. Change/Swap the pointers of the first two nodes and similarly swap the next two nodes until the end of the Linked List.
  3. Maintain a while loop and traverse the Linked List until the end by linking nodes in the swapped manner as mentioned in the above step.

 

Implementation in C++ 

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

struct Node
{
	int key;
	struct Node *next;
};



// Function to perform the swap.
Node *pairWiseSwap(Node *root)
{

	if (root == NULL || root->next == NULL)
		return root;

	Node *curr = root->next->next;
	Node *prev = root;
	root = root->next;
	root->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 root;
}

void push(struct Node** head, int data)
{
	struct Node* node = new Node;
	node->key = data;
	node->next = (*head);
	(*head) = node;
}

void print(struct Node *root)
{
	while (root != NULL)
	{
		cout << root->key << " ";
		root = root->next;
	}
}

int main()
{
	struct Node *head = NULL;

	push(&head, 1);
	push(&head, 2);
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);

	cout << "\n Linked List before ";
	print(head);

	head = pairWiseSwap(head);

	cout << "\n Linked List after  ";
	print(head);

	return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Output:

output

Time Complexity: O(N)

Recursive Approach

 

The idea is to swap two nodes and recursively call the same function on the remaining nodes.

Implementation in C++ 

Node *pairWiseSwap(Node *head) {
        
        if(!head || !head->next) 
              return head;
        
        Node* newhead = head->next;
        Node* next = newhead->next;
        newhead->next = head;
        head->next = pairWiseSwap(next);
        
        return newhead;
        
    }
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

output

Time Complexity: O(N)

Frequently Asked Questions

What is a linked list?

A linked list is a linear data structure that is formed by connected nodes. Each node has a value associated with it and the pointer(s) to its directly connected node(s).   

What is the key difference between a singly linked list and a doubly-linked list?

A singly-linked list is unidirectional, which means that the node of a singly-linked list contains the pointer to its next node only. In contrast, a doubly-linked list is bidirectional, and its node contains the pointer to its next and previous nodes.

Which approach iterative or recursive is better to be considered?

In the recursive function, function calls are stored in the stack and so if the number of nodes will be larger, we can get a “stack overflow” error. Thus the iterative approach is better to be considered.

Conclusion

Here we saw how to pairwise swap adjacent nodes of a Linked List by changing pointers. 

Challenge: Can you solve it by swapping the node’s data instead of pointers? 

Recommended Problems -

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