'How to understand head->next->next = head; for reverse single list by Recursion?

A signle link list, i want revese it by recursion. but i don't understand the meaning of this line head->next->next = head;.

why there need head->next->next?

struct Node{
    int data;
    Node* next;
};

Here is the implement code:

Node* reverseByRecursion(Node *head)
{

    if(head == NULL || head->next == NULL) 
        return head;

    Node *newHead = reverseByRecursion(head->next);

    head->next->next = head;
    head->next = NULL;

    return newHead;    
}
algorithmrecursionlinked-list


Solution 1:[1]

Let me work with this list.

initial list

  1. reverseByRecursion(node1) is called.
  2. Neither node1 nor node1->next is NULL, so newHead = reverseByRecursion(head2); is called.
  3. Neither node2 nor node2->next is NULL, so newHead = reverseByRecursion(head3); is called.
  4. head3->next is NULL, so head3 is returned from reverseByRecursion(head2).
  5. head = node2 and head->next = node3, so head->next->next = head; will set node3->next to node2.
  6. head->next = NULL; will set node2->next to NULL. (image 2)
  7. newHead, which is node3, is returned from reverseByRecursion(head2).
  8. head = node1 and head->next = node2, so head->next->next = head; will set node2->next to node1.
  9. head->next = NULL; will set node1->next to NULL. (image 3)
  10. newHead, which is node3, is returned from reverseByRecursion(node1).
  11. Now the list is reversed with having node3 as the head.

image 2
modified list

image 3
reversed list

Solution 2:[2]

Your base case says that if there are no more elements, then the current node becomes the head of the list.

The head->next->next = head line means that the next node is being reused with its pointer pointing backward (in the opposite direction as before). Since the node used to be the NEXT node after the current node, it becomes the PREVIOUS node before the current head, and its next pointer therefore ought to point to the current node ("head").

Solution 3:[3]

try to understand it this way, .next actually meant to change the arrow pointing to the next value. So

head.next.next = head

means adding an arrow from the next next position and point it back to head

Hope this is more intuitive to understand

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 MikeCAT
Solution 2 Robert Columbia
Solution 3 Roll20

Related Questions