Last Updated on November 8, 2022 by Prepbytes

### Introduction

This blog will give a detailed explanation to swap kth nodes from beginning in linked list with kth nodes from ends in linked list. Swapping the Kth node from the beginning and ending from the linked list will help you to understand the linked list in detail. 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 To Swap Kth Nodes From End In Linked List With Kth Nodes From Beginning In Linked List

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 To Swap Kth Nodes From Beginning In Linked List With Kth Nodes From Ends In Linked List

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 To Swap Kth Nodes From Beginning In Linked List With Kth Nodes From Ends In Linked List

- 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 To Swap Kth Nodes From Beginning In Linked List With Kth Nodes From Ends In Linked List

### Code Implementation To Swap Kth Nodes From Beginning In Linked List With Kth Nodes From Ends In Linked List

#include <stdio.h> #include <stdlib.h> struct Node { int data; struct 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) { printf("%d ",node->data); node = node->next; } printf("\n"); } /* 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; struct Node* x = *head; struct Node* x_prev = NULL; for (int i = 1; i < K; i++) { x_prev = x; x = x->next; } struct Node* y = *head; struct 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; struct Node* temp = x->next; x->next = y->next; y->next = temp; if (K == 1) *head = y; if (K == len) *head = x; } int main() { struct Node* head = NULL; push_node(&head,10); push_node(&head,8); push_node(&head,6); push_node(&head,4); push_node(&head,2); printf("Our original Linked List: "); printLinkedList(head); int K = 2; swapKthnode(&head,K); printf("Linked List after swapping: "); printLinkedList(head); return 0; }

#include <bits stdc++.h=""> 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; }

class Node { int data; Node next; Node(int d) { data = d; next = null; } } class SwapKth { Node head; void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } void printList() { Node node = head; while (node != null) { System.out.print(node.data + " "); node = node.next; } System.out.println(""); } /* Utility function for calculating length of linked list */ int countNodes() { int count = 0; Node s = head; while (s != null) { count++; s = s.next; } return count; } /* Function for swapping kth nodes from both ends of linked list */ void swapKth(int k) { // Count nodes in linked list int n = countNodes(); // Check if k is valid if (n < k) return; // If x (kth node from start) and // y(kth node from end) are same if (2 * k - 1 == n) return; // Find the kth node from beginning of linked list. // We also find previous of kth node because we need // to update next pointer of the previous. Node x = head; Node x_prev = null; for (int i = 1; i < k; i++) { x_prev = x; x = x.next; } // Similarly, find the kth node from end and its // previous. kth node from end is (n-k+1)th node // from beginning Node y = head; Node y_prev = null; for (int i = 1; i < n - k + 1; i++) { y_prev = y; y = y.next; } // If x_prev exists, then new next of it will be y. // Consider the case when y->next is x, in this case, // x_prev and y are same. So the statement // "x_prev->next = y" creates a self loop. This self // loop will be broken when we change y->next. if (x_prev != null) x_prev.next = y; // Same thing applies to y_prev if (y_prev != null) y_prev.next = x; // Swap next pointers of x and y. These statements // also break self loop if x->next is y or y->next // is x Node temp = x.next; x.next = y.next; y.next = temp; // Change head pointers when k is 1 or n if (k == 1) head = y; if (k == n) head = x; } // Driver code to test above public static void main(String[] args) { SwapKth llist = new SwapKth(); for (int i = 8; i >= 1; i--) llist.push(i); System.out.print("Original linked list: "); llist.printList(); System.out.println(""); for (int i = 1; i < 9; i++) { llist.swapKth(i); System.out.println("Modified List for k = " + i); llist.printList(); System.out.println(""); } } }

class Node: def __init__(self, data, next = None): self.data = data self.next = next class LinkedList: def __init__(self, *args, **kwargs): self.head = Node(None) def push(self, data): node = Node(data) node.next = self.head self.head = node def printList(self): node = self.head while node.next is not None: print(node.data, end = " ") node = node.next def countNodes(self): count = 0 node = self.head while node.next is not None: count += 1 node = node.next return count def swapKth(self, k): n = self.countNodes() if n<k: return if (2 * k - 1) == n: return x = self.head x_prev = Node(None) for i in range(k - 1): x_prev = x x = x.next y = self.head y_prev = Node(None) for i in range(n - k): y_prev = y y = y.next if x_prev is not None: x_prev.next = y if y_prev is not None: y_prev.next = x temp = x.next x.next = y.next y.next = temp if k == 1: self.head = y if k == n: self.head = x llist = LinkedList() llist.push(10) llist.push(8) llist.push(6) llist.push(4) llist.push(2) print("Our original Linked List:", end = " ") llist.printList() llist.swapKth(2) print("\nLinked List after swapping:", end = " ") llist.printList() print("\n")

#### Output

Our original Linked List: 2 4 6 8 10

Linked List after swapping: 2 8 6 4 10

**Time Complexity To Swap Kth Nodes From Beginning In Linked List With Kth Nodes From Ends In Linked List**: O(n), Traversing the list requires O(n) time.

In this blog, we have tried to explain the most efficient way to swap kth nodes from beginning in linked List with kth nodes from ends in 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.

## FAQ

- How do you swap data between two nodes in a linked list?
- Can you swap on a linked list?
- What is swapping explain with example?

The idea is to first search x and y in the given linked list. If any of them is not present, then return. While searching for x and y, keep track of current and previous pointers. First change next of previous pointers, then change next of current pointers.

We can swap nodes of linked list either by swapping their data or by changing the links (swapping nodes).

Swapping refers to the exchange of two or more things. For example, in programming data may be swapped between two variables, or things may be swapped between two people.