How to swap Kth node from the beginning with Kth node from the end in the given Singly Linked List

Gorakhnath yadav
Last Updated: May 13, 2022

Introduction

This blog discusses how to swap Kth node from the beginning with 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 Kth node from the beginning with Kth node from the end in the linked list on the top for k=2. Then we have the modified, linked list below it.

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; 

    }

}

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

  1. 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.
     
  2. 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.
     
  3. 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
     
  4. 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.
     
  5. 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.

Key takeaways

In this blog, we learned to swap Kth node from the beginning with 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. 

You can learn more about the linked lists and also practice similar problems on the CodeStudio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think