Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
How do you swap data in two nodes of a linked list?
3.2.
Can we swap entire nodes in a linked list?
3.3.
How do you swap two nodes in a linked list in C++?
3.4.
How do you swap two nodes in a doubly-linked list?
3.5.
What is pairwise swapping a linked list?
4.
Conclusion
Last Updated: Mar 27, 2024
Hard

How to Swap Kth Node from the Beginning with Kth Node from the End in the given Singly Linked List

Linked List

Introduction

This blog discusses how to swap the Kth node from the beginning with the Kth node from the end in the given singly linked list. One very important thing to note here is that while Kth node from the beginning with Kth node from the end we need to swap the node, not only its data. Let’s see the example given below. Suppose we are asked to swap the Kth node from the beginning with the Kth node from the end in the linked list on the top for k=2. Then we have the modified, linked list below it.

Also see, Data Structures and Rabin Karp Algorithm

Illustration Image Swapping

Recommended Topic, Floyds Algorithm

Approach

To swap Kth node from the beginning with Kth node from the end in a linked list, we traverse through it to find the Kth node and (total node- K +1)th node from the beginning, and then we use four temporary variables to store both these nodes and their previous nodes. Then we update the next pointer of the previous node of the first node with the pointer to the second node and the next pointer of the previous node of the second node with the pointer to the first node. We interchange the next pointers of both the nodes using another temporary variable. These operations leave us with the final linked list, which contains the asked nodes in swapped manner.

Algorithm

  • Take the linked list from user input.
  • Create a swap function that takes the head of the linked list the number k, and the size of a linked list as arguments,
  • Create four variables to store the Kth node, its previous node, (N-K+1)th node, and its previous node.
  • Change next pointers of previous nodes of Kth and (N-K+1)th node first with (N-K+1)th node and Kth node, respectively.
  • Create a temporary variable and swap the next pointers of Kth and (N-K+1)th node.
  • Print the linked list.

Implementation

//Program to swap Kth node from the beginning with Kth node from the end in a linked list.

#include <bits/stdc++.h>

using namespace std;

//Structure for a node in the linked list.

struct node

{

    int data;

    struct node *next;

};

//Function to swap nodes.

void swap_nodes(struct node** head, int k, int n)

{

//When k is greater than the size of the linked list.

if(n<k)

{

return;

}

//When kth node from the beginning and the end are the same.

if(2*k-1==n)

{

return;

}

//Variables to store the kth node from the beginnning and its 

//previous node.

node* node1= *head;

node* temp1= nullptr;

for(int i=1;i<k;i++)

{

temp1=node1;

node1=node1->next;

}

//Variables to store the kth node from the end and its 

//previous node.

node* node2= *head;

node* temp2= nullptr;

for(int i=1;i<n-k+1;i++)

{

temp2=node2;

node2=node2->next;

}

//Setting the next pointers of the pevious nodes of the 

//swapped nodes.

if(temp1)

{

temp1->next=node2;

}

if(temp2)

{

temp2->next=node1;

}

//Setting the next pointers of the swapped nodes.

node* temp=node1->next;

node1->next=node2->next;

node2->next=temp;

//We need to update head pointers when k is 1 or n.

if(k==1)

{

*head=node2;

}

if(k==n)

{

*head=node1;

}

}

//Function to push nodes into the list.

void push(struct node** head, int new_val)

{

    //Creatng a new node.

    struct node* new_node= new node();

    //Putting the value in the node.

    new_node->data= new_val;

    //Linking the node to the list.

    new_node->next=(*head);

    //Shifting the head pointer to the new node.

    *head= new_node;

}

//Driver function.

int main()

{

    //Creating an empty list.

    struct node* head=nullptr;

    //Enter no  of nodes in the node.

    int size;

    cout<<"Enter the number of nodes in the list- ";

    cin>>size;

    //Pushing the nodes in it.

    cout<<"Enter the nodes in the list- ";

    for(int i=0;i<size;i++)

    {

        int a;

        cin>>a;

        push(&head,a);

    }

    //Taking the value of k as input.

    int k;

    cout<<"Enter the value of k- ";

    cin>>k;

    //Printing the initial linked list.

    cout<<"Initial linked list-"<<endl;

    struct node* p=head;

    while(p!=nullptr)

    {

        cout<<p->data<<" ";

        p=p->next;

    }

    //Function call to swap nodes in the linked list.

    swap_nodes(&head,k,size); 

    cout<<endl;

    //Printing the final linked list.

    cout<<"Final linked list-"<<endl;

    while(head!=nullptr)

    {

        cout<<head->data<<" ";

        head=head->next; 

    }

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

Input-

7
1 2 3 4 5 6 7
2

Output-

Enter the number of nodes in the list- 
Enter the nodes in the list-
Enter the value of k- 
Initial linked list-
7 6 5 4 3 2 1 
Final linked list-
7 2 5 4 3 6 1

Complexity Analysis

The time complexity of the above approach is- O(N), where N is the number of nodes in the linked list.

The space complexity of the above approach is- O(1).

Frequently Asked Questions

How do you swap data in two nodes of a linked list?

We access the first node and store its pointer in a temporary variable. Then access the second node, store its data in another temporary variable, and copy the first node's data in the second node. Then we copy the data in the second temporary variable in the first node.

Can we swap entire nodes in a linked list?

Yes, we can swap entire nodes in a linked list by changing the pointers of their previous nodes and their next pointers.

How do you swap two nodes in a linked list in C++?

Suppose we have the following linked list-
head->node1->node2->node3->node4->node5->node6->node7->node8->null.
And we have to swap node 2 with node 6, and we create four temporary variables to store node 1, node 2, next pointer of node two, i.e., node 3, node 5. Now, we change the next pointer of node 1 to node six and next to node 5 to node 2. And change the next pointer of node 2 to the next pointer of node 6, then change the next pointer of node 6 to node 3. The updated list will be- 
head->node1->node6->node3->node4->node5->node2->node7->node8->null

How do you swap two nodes in a doubly-linked list?

We swap two nodes doubly linked list similarly as we have swapped two nodes in a singly linked list. The only additional step is updating the previous pointer of the swapped nodes and their next nodes.

What is pairwise swapping a linked list?

Pairwise swapping in a linked list refers to the swapping of consecutive elements. Each pair of adjacent nodes in a linked list are swapped among themselves.

Conclusion

In this blog, we learned to swap the Kth node from the beginning with the Kth node from the end in the given Singly Linked List. 

We start with finding the length of the linked list with a simple traversal in case it is not given. Then we create a function that takes the head of the linked list, its size, and integer k as arguments and first traverses the linked list to find the pointers to both the nodes and their previous nodes. Then we update the next pointer of previous nodes of both the nodes. Then we swap the next pointer of both the nodes. And finally, print the linked list. 

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.

Live masterclass