Tuesday, March 12, 2013

Algorithm to Reverse Linked List - Classic

This is a classic programming puzzle, posed to many and different palces.

Companies in love with this question: Adobe, Microsft, Amazon, Microsoft
Google has changed this question. (in some other post)
Facebook asks an implementation of this in another problem (That Facebook puzzle and its solution some other time)

Answer:


start : iterative loop 
curr->next = prev; 
prev = curr;
 
curr = next;
 
next = curr->next
 
endloop

Another solution can be by using Recursive function:
Just watch the "Base condition" of this algorithm
recursive_solution(ptr) 
if (ptr->next == NULL)
 
return ptr;
 
temp = recursive_solution(ptr->next);
 
temp->next = ptr;
 
return ptr;
 
end

No comments:

Post a Comment