Amazon Interview Question: Reverse linked list recursive... | Glassdoor.co.in

Interview Question

Senior Software Engineer Interview Chennai

Reverse linked list recursively.

Answer

Interview Answer

3 Answers

0

# 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
    list.
    '''
    # 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']:
        print_list(node['next'])

# Test code.
print 'Forward list:',
print_list(forward_list)

print

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

llvllatrix on 16-Jun-2012
1

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
0

/*
     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;
        p1->next=phead;
        phead->next=NULL;
        phead=reverseRecHelper(p1,p2);
    }

    //Auxiliary method for void reverseRec(node* &phead)
    node* reverseRecHelper(node* &p1, node* &p2){
         if(p2==NULL) return p1;
         node* p3=p2->next;
         p2->next=p1;
         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.