Swap Every Kth Node in a LinkedList

Objective: Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched.

Input: A linked list, A number k.

Example:

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 Pointers, 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 swapping so move pointers only k-2 times.
    • Create another pointer , NewHead and point it to ptrTwo.next.
    • Now we have ptrOne at head and ptrTwo at kth position, swap them with the help of ptrTwo_prev.
    • This function will returns the head.
    • Now make a recursive call with newHead.

ptrOne.next = reverseNodes(newHead, k);

Swap Evey Kth Node in a linked list

Swap Evey Kth Node in a linked list

Complete 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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • dheeraj singhal

    There is one more little easy solution of the problem-:
    private void swap(Node head,int k) {
    if(head==null || k<2){
    return;
    }
    int i = 2;
    Node first = head;
    Node second = null;
    Node curr = head.next;
    while (curr != null) {
    if (i % k == 0) {
    second = curr;
    int temp = first.data;
    first.data = second.data;
    second.data = temp;
    first = second.next;
    }
    curr=curr.next;
    i++;
    }

    }

%d bloggers like this: