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:

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

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________