/* 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; }

# 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)