CODEWITHSUNDEEP
crecursionlinked-list
Shivam Mishra
Shivam Mishra

Reputation: 51

Explanation for base case return value in recursive linked list reverse algorithm

I am learning how to reverse a linked list recursively. I am confused with the last 4 lines.

 node *reverse_linked_list_rec(node *head){

  if (head->next==NULL){
    return head;
  }
  
  node *smallans= reverse_linked_list_rec(head->next);
 
  node *tail = head->next;
  tail->next = head;
  head->next = NULL;
   
  return smallans;
    
}

Let's say I am reversing

1 2 3 NULL

by recursion, it reaches at 3 NULL and then by base case returns

2 3 NULL

here head=2, smallans=2 (not sure).

Why we are returning smallAns here and how it is changing?

Upvotes: 1

Views: 128

Answers (1)

ggorlen
ggorlen

Reputation: 57165

smallans is a confusing variable name because it's actually the old tail being passed back through the list to become the new head which is ultimately returned to the caller.

Its next pointer changes when these lines execute in the parent function call:

// when head->next->next == NULL ...
node *tail = head->next; // ... `tail` points to the old tail (new head) ...

tail->next = head; // ... and this sets the new tail's next pointer to
                   // the old second-to-last node (new second node).

tail is a misleading name here--I associate a "tail" with a single node that terminates the entire list, not a previous node. new_prev or old_next seem more appropriate here depending on whether you want to name things relative to the node roles in the new list or the original list.

As a minor point, I recommend using if (!head || !head->next) to avoid a potential null pointer dereference.

I'd write the function as follows:

node *reverse_linked_list_rec(node *head) {
  if (!head || !head->next) {
    return head;
  }
  
  node *old_tail = reverse_linked_list_rec(head->next); 
  node *old_next = head->next;
  old_next->next = head;
  head->next = NULL;
  return old_tail;
}

Aside from intellectual curiosity, recursion is a poor choice for linked list operations since it adds function call overhead, you can blow the stack and the logic isn't any easier to follow than iterative, in most cases.

Case in point, here's a complete example with an iterative version:

#include <stdio.h>
#include <stdlib.h>

struct node {
    int id;
    struct node *next;
};

struct node *make_node(int id) {
    struct node *n = malloc(sizeof(*n));

    if (!n) exit(1);

    n->id = id;
    n->next = NULL;
    return n;
}

struct node *reverse_linked_list(struct node *head) {
    struct node *prev = NULL;
    
    for (struct node *curr = head; curr;) {
        struct node *old_next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = old_next;
    }

    return prev;
}

void print_linked_list(struct node *head) {
    for (; head; head = head->next) {
        printf("%d->", head->id);
    }

    puts("");
}

void free_linked_list(struct node *head) {
    while (head) {
        struct node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

int main() {
    struct node *head = make_node(1);
    head->next = make_node(2);
    head->next->next = make_node(3);
    print_linked_list(head); // => 1->2->3->
    head = reverse_linked_list(head);
    print_linked_list(head); // => 3->2->1->
    free_linked_list(head);
    return 0;
}

As another minor point, since the linked list is being mutated I'd probably go for a header like void reverse_linked_list(struct node **head);. Otherwise, it seems too easy to call the non-void function, ignore the return value and wind up with a memory leak or crash when head in the caller scope (which has become a tail pointing to null) is dereferenced.

Upvotes: 3

Related Questions