Swap Kth nodes from ends in java

Swap Kth nodes from ends in java

Given a singly linked list of size N, and an integer K. You need to swap the Kth node from beginning and Kth node from end in linked list.
Note: You need to swap the nodes through the links and not changing the content of the nodes.

Input

The first line contains N, number of nodes in linked list and K, the nodes to be swapped.
The second line contains the elements of the linked list.

Constraints:

1 <= N <= 10^3
1 < K <N

Output

Print the linked list in a new line.

Example

Input:

5 3
1 2 3 4 5

Output:

1 2 3 4 5 

Explanation:

Here k = 3, hence after swapping the 3rd node from beginning and end the new list will be 1 2 3 4 5.

Input:

4 4
1 2 3 4

Output:

4 2 3 1

Explanation:

Here k = 3, hence after swapping the 3rd node from beginning and end the new list will be 1 2 3 4 5.

Solution:–

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

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
public class Main
{
  static Node insertAtTail(Node head, int data)
    {
        Node NewNode=new Node(data);

        if(head==null)
        {
            return NewNode;
        }

        Node currNode=head;
        while(currNode.next!=null)
        {
            currNode=currNode.next;
        }
        currNode.next=NewNode;
        return head;
    }
  static void printlist(Node head)
    {
        Node currNode=head;
        while(currNode!=null)
        {
            System.out.print(currNode.data+" ");
            currNode=currNode.next;
        }
    }
  public static Node swap(Node head, int n, int k)
  {
    if(n<k)
      return head;
    
    if(2*k-1==n)
      return head;

    Node x=head;
    Node xprev=null;
    for(int i=0;i<k-1;i++)
      {
        xprev=x;
        x=x.next;
      }
    Node y=head;
    Node yprev=null;
    for(int i=0;i<n-k;i++)
      {
        yprev=y;
        y=y.next;
      }
    if(xprev!=null)
    {
      xprev.next=y;
    }
    if(yprev!=null)
    {
      yprev.next=x;
    }
    Node temp=x.next;
    x.next=y.next;
    y.next=temp;

    if(k==1)
      head=y;

    if(k==n)
      head=x;

    return head;
  }
	public static void main (String[] args) throws java.lang.Exception
	{
		//your code here
      Scanner sc=new Scanner(System.in);
        Node head=null;
        int n=sc.nextInt();
        int k=sc.nextInt();
        for(int i=0;i<n;i++)
        {
            int data=sc.nextInt();
            head=insertAtTail(head,data);
        }
      head=swap(head,n,k);
      printlist(head);
	}
}

Add a Comment

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