  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

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

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 Kth node from the beginning with the Kth 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 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 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 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 To Swap Kth Nodes From Beginning In Linked List With Kth Nodes From Ends In Linked List

• 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 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;
}
/* Using this function we will print the linked list */
{
while (node != NULL) {
printf("%d ",node->data);
node = node->next;
}
printf("\n");
}
/* Using this function we will calculate the length of linked list */
{
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)
{
if (len < K)
return;
if (2 * K - 1 == len)
return;
struct Node* x_prev = NULL;
for (int i = 1; i < K; i++) {
x_prev = x;
x = x->next;
}
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)
if (K == len)
}
int main()
{
int K = 2;
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;
}

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

/* Using this function we will calculate the length of linked list */
{
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)
{

if (len < K)
return;

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

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

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)
if (K == len)
}

int main()
{
cout << "Our original Linked List: ";
int K = 2;
cout<< "Linked List after swapping: ";
return 0;
}
```
```class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
class SwapKth
{
void push(int new_data)
{
Node new_node = new Node(new_data);
}
void printList()
{
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;
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_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_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)

if (k == n)
}
// 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);

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

def __init__(self, *args, **kwargs):
def push(self, data):
node = Node(data)

def printList(self):
while node.next is not None:
print(node.data, end = " ")
node = node.next

def countNodes(self):
count = 0
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_prev = Node(None)
for i in range(k - 1):
x_prev = x
x = x.next

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:

if k == n:

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

1. How do you swap data between two nodes in a linked list?

2. 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.

3. Can you swap on a linked list?

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

5. What is swapping explain with example?

6. 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.