Interview Question: Linked List

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
This entry was posted in Sample Qs. Bookmark the permalink.

4 Responses to Interview Question: Linked List

  1. Brett says:

    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.
     

  2. Avi says:

    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

  3. Brett says:

    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

  4. James says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s