Recursion - Interview Questions - Question 2

Recursion - Interview Questions - Question 2

Please reverse a singly linked list using a recursion method.

Analysis:

We can view the reverse process in a three steps:

1. sperate the first element from the rest ones;

2. recursively reverse the rest ones;

3. connect the reversed rest linked list with the former first element (which become the last one now).

See the code below:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next) return head;
        ListNode* p=head;
        // recursive call
        head=reverseList(p->next);
        // the former second element becomes the last second one, and
        // needs to pointe to the former head (to be the last one)
        p->next->next=p;
        // make the former head to be the last one
        p->next=NULL;
        return head;
    }
};

Upper Layer