Swap Kth Node from beginning with Kth Node from End

Table of Contents

Problem Statement

In the “Swap Kth Node from beginning with Kth Node from End” problem, we have given a linked list. Swap kth node from beginning_with kth node from the end. We should not swap the values, we should swap pointers.

Example

2
1 2 3 4 5 6

1 5 3 4 2 6

Approach

Given a linked list and a value k, we have to swap the values of the kth node from the starting and the kth node from the end. We don’t know the length of the linked list we only know the value k.

As we don’t know the length we have to iterate to the linked list to find the length. And we store the kth node and in the second iteration, we can find the kth node from the end, i.e, n-kth node where n is the length of the linked list. Or we can use the information given in the question, the distance of the kth node from the end is equal to the distance from the end. In this method, we don’t need to find the length of the linked list.

Firstly we take a curr pointer that points to the head, then move this pointer to the kth node. The take two pointers p1 and p2, p1 points to the head node and p2 points to the curr->next. If we take the above-linked list in the figure as an example then p1 points to the node with value 1, and p2 points to the node with value 3.

Then iterate both p1 and p2 pointers until the p2 pointer becomes null, and we reach the end of the linked list. Then p1 points to the kth node from the end and we have kth-node stored in the curr pointer. We swap the values in the nodes.

Implementation

C++ Program to Swap Kth Node from beginning with Kth Node from End

#include<bits/stdc++.h>
using namespace std;

class MyLinkedList {
public:
    struct ListNode {
        ListNode *next;
        int val;
        ListNode(int a): next(NULL), val(a){}
    };
    ListNode *head;

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    void swapNodes(int k) {
        int len=0;
        ListNode* curr = head;
        for(int i=1;i<k;i++){
            curr = curr->next;
        }
        ListNode* p1 = head,*p2 = curr->next;
        while(p2){
            p1 = p1->next;
            p2=p2->next;
        }
        swap(curr->val,p1->val);
    }

    void print_list(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead(5);
  list->addAtHead(4);
  list->addAtHead(3);
  list->addAtHead(2);
  list->addAtHead(1);
  
  list->print_list();
  list->swapNodes(2);
    list->print_list();
}

Java Program to Swap Kth Node from beginning with Kth Node from End

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
  
  public static void main (String[] args) throws java.lang.Exception{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead(5);
    obj.addAtHead(4);
    obj.addAtHead(3);
    obj.addAtHead(2);
    obj.addAtHead(1);
    
    obj.printList();
    obj.swapNodes(2);
    obj.printList();
    
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          int val = 0;
          
          public Node(int val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      public void addAtHead(int val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
    public void swapNodes(int k) {
          Node A = head, B = head, nodeK;
          for (int i = 1; i < k; i++) A = A.next;
          nodeK = A;
          A = A.next;
          while (A != null) {
              A = A.next;
              B = B.next;
          }
          int temp = nodeK.val;
          nodeK.val = B.val;
          B.val = temp;
          
    }

    public void printList(){
      Node curr = head;
      while(curr!=null){
        System.out.print(curr.val+" ");
        curr = curr.next;
      }
      System.out.println("");
    }
      
  }
}

1 2 3 4 5 
1 4 3 2 5