Sample Question #230 (programming – general)

You’re given a singly-linked list. How do you reverse the linking?

[A real interview question I faced]

Advertisements

Sample Question #230 (programming – general)

You’re given a singly-linked list. How do you reverse the linking?

[A real interview question I faced]

Advertisements

%d bloggers like this:

ANSWER

In a singly-linked list, or slist, each node points to the "next" node only, e.g., A->B->C->D->E. To reverse, you simply traverse the list, save all the existing references, and make each node point to the "previous" node. For node A, you need to find its address for B to point to.

An easy question – I was once asked as a sequel, what happens if the list contains a loop, since in that case (previous answer) the program would run forever. my answer then was that you’d have to check it by saving all addresses etc.Later I realized that inverting a linked list that has a loop is an undefined problem ( i.e. what IS the inverse of a linked list with a loop?).Furthermore, the program won’t run forever. it will stop ( after O(n)) and return the only reasonable thing which can be defined as the inverse of a linked list with a loop

Avi, let’s say we have a linked list A->B->C->D->A. This is a looped slist. Then isn’t the inverted list just A->D->C->B->A? Since a linked list always starts with some "initial" node, I think it’s possible to check for a terminal condition when you invert it, even if it’s looped.

When you have doubly-linked lists, then you won’t have to invert anything…

-brett

link* reverse(link* start){ if (this->next != start) this->next->reverse(start)->next=this; else this->next->next = this; return this; }