Monday, June 15, 2015

Google Question: Reverse linked list without using recursion.

Problem: Reverse the linked list without using recursion.

Solution: It is straight forward, can be easily understood by implementation.

Implementation:

void List::reverse()
{
ListNode *curr = head;
ListNode *next = NULL, *prev = NULL;
while(curr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
}

Complexity: O(n)

No comments:

Post a Comment