TechnicalArchitectureWorx

The (Unofficial) ITWorx Technical Architecture Blog

Interviewing Question: Inserting into a Sorted Linked List

Posted by archworx on February 25, 2007

Due to the popularity of our Interviewing Question posts, we’ve decided to add yet another question. This time its easy and straight forward. You have a singly linked list of integers that are ordered ascendingly (for example -2,1,4,6,7). Can you devise an algorithm by which you insert a node into the linked list while maintaining its order. For example if you want to add a node containing the integer ‘5’ the linked list in the previous example will become (-2,1,4,5,6,7). Can you write the algorithm in C++ ?

Advertisements

14 Responses to “Interviewing Question: Inserting into a Sorted Linked List”

  1. yshahin said

    PRE
    head is a pointer to the head of the list
    node is the link list element

    public void insertSort(node *item)
    {
    node *curr=head, *prev=null;
    while(curr != null)
    {
    if(curr->value >= item->value)
    break;
    prev = curr;
    curr = curr->next;
    }
    if(prev == null)
    {
    item->next = head;
    head = item;
    }
    else
    {
    prev->next = item;
    item->next = curr;
    }
    }

  2. hellboy said

    hah.
    heartily thanks…!

    wasted half-a-day for trying this by my own.
    then i discovered you.

    thanks again!

    more importantly, it worked..!!!
    lol

  3. hiren said

    I think there should be one more condition. what if (curr==null)?

    in that case:
    item->next = null;
    prev->next=item;

    correct me if i am wrong.

    • Manish Singh said

      No it is not needed. what you are talking about is adding a node to an empty list. This condition will be handled by the if( prev == null ) case

  4. It’s in point of fact a great and helpful piece of info. I’m glad that you shared this useful information with us.
    Please stay us informed like this. Thanks for sharing.

  5. Heya i’m for the primary time here. I found this board and I find It truly useful & it helped me out much. I am hoping to offer something again and aid others like you aided me.

  6. Hello, Neat post. There’s an issue with your site in web explorer, may test this? IE nonetheless is the marketplace chief and a big component of other folks will omit your great writing because of this problem.

  7. Wonderful work! That is the type of information that are supposed to be shared around the internet.

    Disgrace on Google for no longer positioning this post higher!
    Come on over and consult with my site . Thanks =)

  8. Does your blog have a contact page? I’m having trouble locating it but, I’d like to shoot you an
    e-mail. I’ve got some creative ideas for your blog you might be interested in hearing. Either way, great site and I look forward to seeing it improve over time.

  9. Nigel said

    It’s remarkable to pay a visit this web page and reading the views of all friends on the topic of this paragraph, while I am also zealous of getting know-how.

  10. Your way of explaining the whole thing in this article is
    really fastidious, every one can without difficulty know it, Thanks
    a lot.

  11. It is truly a great and useful piece of information.

    I am satisfied that you shared this helpful info with us.
    Please keep us informed like this. Thanks for sharing.

  12. It’s actually very difficult in this active life to listen news on Television, so I
    simply use web for that purpose, and get the most
    recent news.

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

 
%d bloggers like this: