Reverse alternate K nodes in a Singly Linked List

Question

I took this question and Java solution from http://www.geeksforgeeks.org/reverse-alternate-k-nodes-in-a-singly-linked-list/

Given a linked list, write a function to reverse every alternate k nodes Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3 Output: 3->2->1->4->5->6->9->8->7->NULL.

In their java code: I really don't understand why step 2) is needed. node is NOT being used anywhere else except in the first argument in kAltReverse(Node node, int k) This node argument in the method is assigned to a new variable current in every recursions. And then use current, prev, next variables in each recursions.

So why node.next = current in step2) is needed?

 Node kAltReverse(Node node, int k) {
    Node current = node;
    Node next = null, prev = null;
    int count = 0;

    /*1) reverse first k nodes of the linked list */
    while (current != null && count < k) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
        count++;
    }

    /* 2) Now head points to the kth node.  So change next 
     of head to (k+1)th node*/
    if (node != null) {
        node.next = current;   **// why node.next should be moved to current even though node is not impacting on anywhere else in 3), 4)???**
    }

    /* 3) We do not want to reverse next k nodes. So move the current 
     pointer to skip next k nodes */
    count = 0;
    while (count < k - 1 && current != null) {
        current = current.next;
        count++;
    }

    /* 4) Recursively call for the list starting from current->next.
     And make rest of the list as next of first node */
    if (current != null) {
        current.next = kAltReverse(current.next, k);
    }

    /* 5) prev is new head of the input list */
    return prev;
}

Sylwester Sylwester · Accepted Answer · 2016-03-22T23:01:13

Your question doesn't really have anything to do with recursion and in this method recursion could have been avoided by simply keeping the first prev and rather wrapped most of the code in a while loop. This question is all about references.

The process rearranges the chain. Just before the code in question you have two linked lists that are not connected:

3->2->1->null 4->5->...
\prev \node   \current

When setting node.next you are altering a property on the object referenced by node. Thus you are replacing the reference to point to a different object. When node.next is used as a value you'll get the reference to an object. After doing node.next = current you have this:

3->2->1->4->5->...
\prev \  \current
       \node

Reverse alternate K nodes in a Singly Linked List

1 Answers