Advertisement
arpit01

Swap Kth nodes from ends

Sep 29th, 2022
1,084
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.30 KB | None | 0 0
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. public class Main
  6. {
  7.  
  8.          // Node class
  9.     static class Node{
  10.        int data; Node next;
  11.        Node(int val)
  12.       {
  13.           data = val;
  14.           next = null;
  15.       }
  16.     }
  17.  
  18.     // function to create a LL
  19.     static Node createLL(int len, int[] arr)
  20.     {
  21.          Node head = null, tail = null;
  22.          for(int i = 0; i<len; i++)
  23.            {
  24.                Node newNode = new Node(arr[i]);
  25.                if(head == null)
  26.                {
  27.                    head = newNode;
  28.                    tail = newNode;
  29.                }
  30.                else
  31.                {
  32.                    tail.next = newNode;
  33.                    tail = newNode;
  34.                }
  35.            }
  36.        return head;
  37.     }
  38.  
  39.     // count he number of nodes
  40.     static int countNodes(Node head)
  41.     {
  42.         int cnt = 0;
  43.         while(head != null)
  44.           {
  45.               cnt++;
  46.               head = head.next;
  47.           }
  48.        return cnt;
  49.     }
  50.  
  51.     // print the LL
  52.     static void printLL(Node head)
  53.     {
  54.        while(head != null)
  55.          {
  56.              System.out.print(head.data+ " ");
  57.              head = head.next;
  58.          }
  59.     }
  60.  
  61.       // Swap the kth nodes from start and end
  62.         static Node swapKthNode(Node head, int n, int k)
  63.         {
  64.                 //base cases
  65.                 if(head == null || head.next == null)
  66.                         return head;
  67.  
  68.                 // no swapping reqd
  69.                 if (k == n-k+1)
  70.                         return head;
  71.                 else
  72.                 {
  73.                         Node first = head, second = head;
  74.                         Node first_prev = null, second_prev = null;
  75.  
  76.                         for(int i = 1; i<k; i++)
  77.                         {
  78.                                 first_prev = first;
  79.                                 first = first.next;
  80.                         }
  81.  
  82.                         for(int i = 1; i<n-k+1; i++)
  83.                         {
  84.                                   second_prev = second;
  85.                                   second = second.next;
  86.                         }
  87.  
  88.                         if(first_prev != null)
  89.                                 first_prev.next = second;
  90.  
  91.                         if(second_prev != null)
  92.                                 second_prev.next = first;
  93.  
  94.                         Node temp = first.next;
  95.                         first.next = second.next;
  96.                         second.next = temp;
  97.  
  98.                         if(k == 1)
  99.                                 head = second;
  100.  
  101.                         if(k == n)
  102.                                 head = first;
  103.  
  104.                 }
  105.                
  106.  
  107.                 return head;
  108.         }
  109.        
  110.     public static void main (String[] args) throws java.lang.Exception
  111.     {
  112.         //your code here
  113.                 Scanner sc = new Scanner(System.in);
  114.                 int n = sc.nextInt();
  115.                 int k = sc.nextInt();
  116.  
  117.                 int arr[];
  118.                  arr = new int[n];
  119.  
  120.                 for(int i = 0; i<n; i++)
  121.                         arr[i] = sc.nextInt();
  122.  
  123.                 Node head = createLL(n, arr);
  124.  
  125.                 head = swapKthNode(head, n, k);
  126.  
  127.                 printLL(head);
  128.     }
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement