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 <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: O(n), Traversing the list requires O(n) time.
[forminator_quiz id=”5024″]

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.

Leave a Reply

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