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
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;
}
}
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).