### 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 K^{th} node from the beginning with the K^{th} 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 K^{th} node from the beginning with the K^{th} 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 2
^{nd}node from the beginning of the linked list is node with value 2 and 2^{nd}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 3
^{rd}node from the beginning of the linked list is node with value 5 and 3^{nd}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 k
^{th}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 K^{th}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 K^{th} node from the beginning of the list with the K^{th} from the end of the list.

### Algorithm

- Iterate the linked list and find the K
^{th}node and (N-K+1)^{th}node from the beginning of the linked list. Also, find the previous nodes of K^{th}node and (N-K+1)^{th}node. - If the previous node of K
^{th}node is not null, connect the previous of K^{th}node to the (N-K+1)^{th}node. Similarly, if (N-K)^{th}node is not null, join this node to the K^{th}node of the linked list.

**Note:**There might be a case if (N-K+1)^{th}node's next is K^{th}node, so in this case (K-1)^{th}node is same as (N-K+1)^{th}node. So the statement**(K-1)**creates a self-loop and this self loop will be broken when we change (N-K+1)^{th}node's next = (N-K+1)^{th}node^{th}node's next. - Swap the next K
^{th}node and (N-K+1)^{th}node. The statements used in swapping also break the self-loop if K^{th}node's next is (N-K+1)^{th}node or (N-K+1)^{th}node's next is K^{th}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 K^{th}node. - Following all the above steps, our nodes will get swapped, and we will have our resultant linked list.

### Dry Run

### Code Implementation

#includeusing 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 K^{th} node from beginning with K^{th} 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.