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