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 Every Kth Node in a LinkedList

Objec­tive: Given a linked list, swap every kth node in that. If at the end of the list remain­ing nodes are less than k, leave them untouched.

Input: A linked list, A num­ber k.

Exam­ple:

Input : ->1->2->3->4->5->6->7->8->9->10 , K = 4
Output: ->4->2->3->1->8->6->7->5->9->10

Approach:

    • Take 3 Point­ers, ptrOne, ptrTwo and ptrTwo_prev.
    • ptrOne and ptrTwo_prev points at head node.
    • ptrTwo points at next node of ptrTwo_prev.
    • Move the ptrTwo and ptrTwo_prev k-2 times, since we need one pointer each at both ends for swap­ping so move point­ers only k-2 times.
    • Cre­ate another pointer , New­Head and point it to ptrTwo.next.
    • Now we have ptrOne at head and ptrTwo at kth posi­tion, swap them with the help of ptrTwo_prev.
    • This func­tion will returns the head.
    • Now make a recur­sive call with newHead.

ptrOne.next = reverseNodes(newHead, k);

Swap Evey Kth Node in a linked list

Swap Evey Kth Node in a linked list

Com­plete Code:

Output:
Original Link List 1 : ->1->2->3->4->5->6->7->8->9->10
Swap Every 4th Node :
->4->2->3->1->8->6->7->5->9->10

You may also like...