Swap Kth Node from the front with the Kth Node from the End

by

Objective: Given a Linked List and a number k, Swap Kth Node from the front with the Kth Node from the End

Example:

->10->20->30->40->50->60->70
Swapping 1 Node from the Front and from the End
->70->20->30->40->50->60->10
Swapping 2 Node from the Front and from the End
->70->60->30->40->50->20->10 
Swapping 3 Node from the Front and from the End
->70->60->50->40->30->20->10 
k = 4, Nodes are same from front and at the end, no swapping
->70->60->50->40->30->20->10 
Swapping 5 Node from the Front and from the End
->70->60->30->40->50->20->10
Swapping 6 Node from the Front and from the End
->70->20->30->40->50->60->10
Swapping 7 Node from the Front and from the End
->10->20->30->40->50->60->70

INVALID NUMBER, No Swapping, k>length of list
->10->20->30->40->50->60->70

Approach:

  • Find the length of the list, say it is ‘Len’.
  • If k>Len, No Swapping.
  • If kth node from the front and the end are same (2*k-1=Len), No Swapping.
  • If above two steps are not true then we need swapping of the elements.
  • Take a pointer left, move it by k nodes. Keep track of node prior to left( call it as left_prev, we need it for the swapping).
  • Set left_prev = null if k=1.
  • Take a pointer right, move it by len-k+1 nodes(it will be the kth node from the end). Keep track of node prior to left( call it as right_prev, we need it for the swapping).
  • Set right_prev = null if k=Len.
  • If left_prev!=NULL means left node is not the first node, so make left_prev will point to right
  • If right_prev!=NULL means right node is not the first node, so right_prev will point to left node.
  • Now just swap the next and right.next to complete the swapping.
  • NOTE:We need to change the head of list if k =1 (head = right) or k = len (head = left).

Complete Code:

public class swap_ith_Element_FromFrontAndEnd {
public int len;
public Node head;
public swap_ith_Element_FromFrontAndEnd() {
head = null;
}
public static void main(String[] args) throws java.lang.Exception {
swap_ith_Element_FromFrontAndEnd a = new swap_ith_Element_FromFrontAndEnd();
a.addAtEnd(10);
a.addAtEnd(20);
a.addAtEnd(30);
a.addAtEnd(40);
a.addAtEnd(50);
a.addAtEnd(60);
a.addAtEnd(70);
a.display();
for (int x = 1; x < 9; x++) {
a.swapNode(x);
a.display();
}
}
public Node swapNode(int i) {
len = getLength(head);
if (i > len) {
System.out.println("\n INVALID NUMBER, No Swapping, k>length of list");
return null;
}
if (2 * i – 1 == len) {
System.out.println("\nk = " + i + ", Nodes are same from front and at the end, no swapping");
return null; // both are same, No need for swaping
}
System.out.println("\nSwapping " + i
+ " Node from the Front and from the End");
Node left = head;// move from left i nodes, in case i=1=>left_prev=NULL
Node left_prev = null;
int j = i;
while (j > 1) {
left_prev = left;
left = left.next;
j—;
}
// System.out.println("\nleft pointing at " + left.data);
Node right = head;// move j=(len-i+1) from the start, which means i
// nodes from the end
Node right_prev = null;// in case i=len=> right will the first node =>
// right_prev=NULL
j = len – i + 1;
while (j > 1) {
right_prev = right;
right = right.next;
j—;
}
// System.out.println("right pointing at " + right.data);
if (left_prev != null) {// if left_prev!=NUll=>left node is not the
// first node, so left_prev will point to right node
left_prev.next = right;
}
if (right_prev != null) {// if right_prev!=NUll=>right node is not the
// first node, so right_prev will point to left node
right_prev.next = left;
}
Node temp = left.next;// now just swap the left.next and right.next to
// complete
left.next = right.next;
right.next = temp;
if (i == 1)// change the head in case of i=1 or i=len.
head = right;
if (i == len)
head = left;
return head;
}
public int getLength(Node head) {
Node n = head;
int count = 0;
while (n != null) {
n = n.next;
count++;
}
return count;
}
public void addAtEnd(int data) {
Node n = new Node(data);
if (head == null) {
n.next = head;
head = n;
} else {
Node currNode = head;
while (currNode.next != null) {
// System.out.print("—->" + currNode.data);
currNode = currNode.next;
}
currNode.next = n;
}
}
public void display() {
// System.out.println("");
Node currNode = head;
while (currNode != null) {
System.out.print("->" + currNode.data);
currNode = currNode.next;
}
}
}
class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}

view raw
swap_ith_Element_FromFrontAndEnd.java
hosted with ❤ by GitHub


Output:

->10->20->30->40->50->60->70
Swapping 1 Node from the Front and from the End
->70->20->30->40->50->60->10
Swapping 2 Node from the Front and from the End
->70->60->30->40->50->20->10
Swapping 3 Node from the Front and from the End
->70->60->50->40->30->20->10
k = 4, Nodes are same from front and at the end, no swapping
->70->60->50->40->30->20->10
Swapping 5 Node from the Front and from the End
->70->60->30->40->50->20->10
Swapping 6 Node from the Front and from the End
->70->20->30->40->50->60->10
Swapping 7 Node from the Front and from the End
->10->20->30->40->50->60->70
 INVALID NUMBER, No Swapping, k>length of list
->10->20->30->40->50->60->70

Related Posts: