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
