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

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..-

Google Microsoft Amazon Facebook more..

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

You may also like...

  • dheeraj singhal

    why not simply swap left and right nodes element instead of keeping track of prev nodes and changing pointers?

    • tutorialhorizon

      swapping nodes elements, means just swapping the data of the nodes??? if that is what you mean then we need to swap the nodes (nodes has references and memories)…by changing the element or data , we will be having the unchanged nodes with different values.

%d bloggers like this: