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 the right node is not the first node, so right_prev will point to the 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).

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

Related Posts: