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

  • dheeraj sing­hal

    why not sim­ply swap left and right nodes ele­ment instead of keep­ing track of prev nodes and chang­ing pointers?

    • tuto­ri­al­hori­zon

      swap­ping nodes ele­ments, means just swap­ping the data of the nodes??? if that is what you mean then we need to swap the nodes (nodes has ref­er­ences and memories)…by chang­ing the ele­ment or data , we will be hav­ing the unchanged nodes with dif­fer­ent values.