Swap Kth node from beginning with Kth node from end in the given Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a LinkedList and are asked to swap the Kth node from the beginning with the Kth node from the end in the linked list.

Problem Statement Understanding

According to the problem statement, a LinkedList is given and we need to swap the Kth node from the beginning with the Kth node from the end in the linked list.

Let’s try to understand the problem statement with the help of examples.

If the given Linked List is: head β†’ 1 β†’ 2 β†’ 3 β†’ 4 β†’5 and K = 2.

  • As we can see, that 2nd node from the beginning of the linked list is node with value 2 and 2nd node from the end of the linked list is node with value 4, so now according to the problem these two nodes needs to be swapped.
  • Our output Linked List after swapping the nodes will look like: head β†’1 β†’ 4 β†’ 3 β†’ 2 β†’5

If the linked list is: head β†’ 1 β†’ 3 β†’ 5 β†’ 7 β†’ 9 β†’ 11 β†’ 13 β†’ 15 and K = 3.

  • In this 3rd node from the beginning of the linked list is node with value 5 and 3nd node from the end of the linked list is node with value 11, so after swapping these nodes, our output linked list will look like: head β†’ 1 β†’ 3 β†’ 11 β†’ 7 β†’ 9 β†’ 5 β†’ 13 β†’ 15.
Some more examples

Sample Input 1: head β†’ 1 -> 2 -> 3 -> 4 -> 5 -> 6 and K = 5
Sample output 1: head β†’ 1 -> 5 -> 3 -> 4 -> 2 -> 6

Sample Input 2: head β†’ 2 -> 4 -> 6 -> 8 -> 10 -> 12 and K = 3
Sample output 2: head β†’ 2 -> 4 -> 8 -> 6 -> 10 -> 12

Note: Here, we are taking one-based indexing in the above examples.

Now I think from the above example, the problem statement is clear. So let's see how we will approach it.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach the problem in the next section.

Let’s move to the approach section.

Approach

Our approach will be simple:

  • To solve this problem, we simply find the kth node from the starting and end and will also keep track of their previous nodes, which will help us to make connections between the nodes while swapping.
  • Also, remember that (N-K+1)th node (N is the length of the linked list) from the starting will be the Kth node from the last. We will also utilize this information.

Let's move to the algorithm section to see all the steps we will be performing while swapping the Kth node from the beginning of the list with the Kth from the end of the list.

Algorithm

  • Iterate the linked list and find the Kth node and (N-K+1)th node from the beginning of the linked list. Also, find the previous nodes of Kth node and (N-K+1)th node.
  • If the previous node of Kth node is not null, connect the previous of Kth node to the (N-K+1)th node. Similarly, if (N-K)th node is not null, join this node to the Kth node of the linked list.
    Note: There might be a case if (N-K+1)th node's next is Kth node, so in this case (K-1)th node is same as (N-K+1)th node. So the statement (K-1)th node's next = (N-K+1)th node creates a self-loop and this self loop will be broken when we change (N-K+1)th node's next.
  • Swap the next Kth node and (N-K+1)th node. The statements used in swapping also break the self-loop if Kth node's next is (N-K+1)th node or (N-K+1)th node's next is Kth node.
  • If our K == 1, we will change our head pointer to (N-K+1)th node, but if K == N, we will change head to Kth node.
  • Following all the above steps, our nodes will get swapped, and we will have our resultant linked list.

Dry Run


Code Implementation

#include 
using namespace std;

/* Linked List Node structure */
struct Node {
	int data;
	Node* next;
};

/* Using this function we will insert a new node at the head of linked list */
void push_node(struct Node** head, int data)
{
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
	new_node->data = data;
	new_node->next = (*head);
	(*head) = new_node;
}

/* Using this function we will print the linked list */
void printLinkedList(struct Node* node)
{
	while (node != NULL) {
		cout << node->data << " ";
		node = node->next;
	}
	cout << endl;
}

/* Using this function we will calculate the length of linked list */
int lenLinkedList(struct Node* for_len)
{
	int count = 0;
	while (for_len != NULL) {
		count++;
		for_len = for_len->next;
	}
	return count;
}

/* Using this function we will swap the Kth node from beginning with the Kth node from end */
void swapKthnode(struct Node** head, int K)
{
	int len = lenLinkedList(*head);

	if (len < K)
		return;

	if (2 * K - 1 == len)
		return;

	Node* x = *head;
	Node* x_prev = NULL;
	for (int i = 1; i < K; i++) {
		x_prev = x;
		x = x->next;
	}

	Node* y = *head;
	Node* y_prev = NULL;
	for (int i = 1; i < len - K + 1; i++) {
		y_prev = y;
		y = y->next;
	}

	if (x_prev)
		x_prev->next = y;

	if (y_prev)
		y_prev->next = x;

	Node* temp = x->next;
	x->next = y->next;
	y->next = temp;

	if (K == 1)
		*head = y;
	if (K == len)
		*head = x;
}

int main()
{
  Node* head = NULL;
  push_node(&head,10);
  push_node(&head,8);
  push_node(&head,6);
  push_node(&head,4);
  push_node(&head,2);
  cout << "Our original Linked List: ";
  printLinkedList(head);
  int K = 2;
  swapKthnode(&head,K);
  cout<< "Linked List after swapping: ";
  printLinkedList(head);
	return 0;
}

Output

Our original Linked List: 2 4 6 8 10
Linked List after swapping: 2 8 6 4 10

Time Complexity: O(n), Traversing the list requires O(n) time.

So, in this blog, we have tried to explain the most efficient way to swap Kth node from beginning with Kth node from the end in a Linked List. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Sort a Linked List of 0s, 1s and 2s
Next post Doubly Circular Linked List Introduction and Insertion

Leave a Reply

Your email address will not be published. Required fields are marked *