Amazon Interview Question: Reverse linked list recursive... |

Interview Question

Senior Software Engineer Interview Chennai

Reverse linked list recursively.


Interview Answer

3 Answers


# A pythonic linked list.
forward_list = {
    'value': 'a',
    'next': {
        'value': 'b',
        'next': {
            'value': 'c',
            'next': None

def reverse_list(node):
    Reverses a linked list. Returns the supplied node and the new head of the
    # The new head of the list.
    head = node

    # If we're not at the end, reverse the next nodes and add this node to the
    # chain.
    if node['next']:
        result, head = reverse_list(node['next'])
        result['next'] = node
        node['next'] = None

    # If we're at the end, this statement is the base case; return the newly
    # reversed list.
    return node, head

def print_list(node):
    print node['value'],
    if node['next']:

# Test code.
print 'Forward list:',


# Print the reverse list.
print 'Reverse list:',
old_head, new_head = reverse_list(forward_list)

llvllatrix on 16-Jun-2012

Node * reverse( Node * ptr , Node * previous) {
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        return ptr;
    } else {
        temp = reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
reversedHead = reverse(head, NULL);

devsathish on 17-Aug-2012

     Jun Zheng, Rice Univ
     C++, Xcode 4.5.2
     Reverse a linked list recursively
     Real interview question of Amazon & Schlumberger
    void reverseRec(node* &phead){
        if(phead==NULL ||phead->next==NULL) return;
        node* p1=phead->next;
        node* p2=p1->next;

    //Auxiliary method for void reverseRec(node* &phead)
    node* reverseRecHelper(node* &p1, node* &p2){
         if(p2==NULL) return p1;
         node* p3=p2->next;
         p1=reverseRecHelper(p2, p3);
         return p1;

Jun Zheng on 04-Mar-2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.