Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given a Linked List and a num­ber k, Swap Kth Node from the front with the Kth Node from the End

Exam­ple:

->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 swap­ping 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 com­plete the swapping.
  • NOTE:We need to change the head of list if k =1 (head = right) or k = len (head = left).

Com­plete Code:


Out­put:

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

You may also like...