Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3667 > unrolled thread

reversing a singly linked list

Back to article view | Back to comp.programming

Contents

  reversing a singly linked list bob <bob@coolfone.comze.com> - 2013-08-19 17:57 -0700
    Re: reversing a singly linked list Ian Collins <ian-news@hotmail.com> - 2013-08-20 13:22 +1200
    Re: reversing a singly linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-08-20 02:26 +0100
    Re: reversing a singly linked list Robert Wessel <robertwessel2@yahoo.com> - 2013-08-19 21:19 -0500
      Re: reversing a singly linked list bob <bob@coolfone.comze.com> - 2013-08-22 22:21 -0700
    Re: reversing a singly linked list James Dow Allen <jdallen2000@yahoo.com> - 2013-08-22 04:11 -0700
      Re: reversing a singly linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-08-22 12:57 +0100
        Re: reversing a singly linked list James Dow Allen <jdallen2000@yahoo.com> - 2013-08-22 09:30 -0700

#3667 — reversing a singly linked list

Just out of curiosity, if someone asks you to write code to reverse a singly linked list at an interview, could you do it? (in C/C++)

I struggled with this, and I'm not sure if it was a hard question or not.

Thanks.

[toc] | [next] | [standalone]

#3668

bob wrote:

{please clean up the mess google will inevitably make of your replies!}

> Just out of curiosity, if someone asks you to write code to reverse a
> singly linked list at an interview, could you do it? (in C/C++)

Which one, C or C++?

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#3669

bob <bob@coolfone.comze.com> writes:

> Just out of curiosity, if someone asks you to write code to reverse a
> singly linked list at an interview, could you do it? (in C/C++)

I'd call it a daft question.  This is what you should do in C++:

  std::list<int> a_list;
  // populate it...
  a_list.reverse();

but C++'s list type is not singly linked, so you might be criticised for
doing it right!

> I struggled with this, and I'm not sure if it was a hard question or
> not.

In C you have to write the code that the interviewer wants you to write,
so the question should probably have specified C.  Adding C++ just makes
it sound like you are being asked not to use the language properly.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#3670

On Mon, 19 Aug 2013 17:57:20 -0700 (PDT), bob <bob@coolfone.comze.com>
wrote:

>Just out of curiosity, if someone asks you to write code to reverse a singly linked list at an interview, could you do it? (in C/C++)
>
>I struggled with this, and I'm not sure if it was a hard question or not.


Just run the list, and change all the link pointers to point to the
previously encountered item.  IOW:

  item *pp, *np, *tp;

  pp = NULL;
  np = headoflistpointer;
  while (np)
    {
    tp = np->next; 
    np->next = pp;
    pp = np;
    np = tp;
    }

  headoflistpointer = pp;

That assumes the task is to do the reverse in-place.

[toc] | [prev] | [next] | [standalone]

#3682

On Monday, August 19, 2013 9:19:18 PM UTC-5, robert...@yahoo.com wrote:
> On Mon, 19 Aug 2013 17:57:20 -0700 (PDT), bob <bob@coolfone.comze.com>
> 
> wrote:
> 
> 
> 
> >Just out of curiosity, if someone asks you to write code to reverse a singly linked list at an interview, could you do it? (in C/C++)
> 
> >
> 
> >I struggled with this, and I'm not sure if it was a hard question or not.
> 
> 
> 
> 
> 
> Just run the list, and change all the link pointers to point to the
> 
> previously encountered item.  IOW:
> 
> 
> 
>   item *pp, *np, *tp;
> 
> 
> 
>   pp = NULL;
> 
>   np = headoflistpointer;
> 
>   while (np)
> 
>     {
> 
>     tp = np->next; 
> 
>     np->next = pp;
> 
>     pp = np;
> 
>     np = tp;
> 
>     }
> 
> 
> 
>   headoflistpointer = pp;
> 
> 
> 
> That assumes the task is to do the reverse in-place.

Yeah, there's a book on Amazon called

Elements of Programming Interviews: 300 Questions and Solutions

It pretty much has the solution you just gave with different variable names.

Thanks.

[toc] | [prev] | [next] | [standalone]

#3679

This reminds me of a thread I started in this
ng 9 years ago, titled "Fast pancake flipping."

In <266426e1.0402180324.56d31715 % posting.google.com>
I posed a puzzle (not just to reverse the list, but
to do so in O(1) time);
in <266426e1.0402230103.5ea4d484 % posting.google.com>
I posted a partial spoiler.

Are such 9-year old Usenet messages easily accessible?
("Don't be evil, Inc." may have pretty well sabotaged
the interface to its own archives.)

(In the message ID's above, I added spaces before and
after the '%' symbols, as required since I'm posting
from the interface of "Don't be evil, Inc."

James Dow Allen

[toc] | [prev] | [next] | [standalone]

#3680

James Dow Allen <jdallen2000@yahoo.com> writes:

> This reminds me of a thread I started in this
> ng 9 years ago, titled "Fast pancake flipping."
>
> In <266426e1.0402180324.56d31715 % posting.google.com>
> I posed a puzzle (not just to reverse the list, but
> to do so in O(1) time);
> in <266426e1.0402230103.5ea4d484 % posting.google.com>
> I posted a partial spoiler.
>
> Are such 9-year old Usenet messages easily accessible?
> ("Don't be evil, Inc." may have pretty well sabotaged
> the interface to its own archives.)

Currently, yes.  Using the message ID search on this page

http://groups.google.com/advanced_search

I found

https://groups.google.com/forum/#!topic/comp.programming/hF6-FXky2-k

right away.  How long the advanced search will remain is, of course,
unknown to people like me.

> (In the message ID's above, I added spaces before and
> after the '%' symbols, as required since I'm posting
> from the interface of "Don't be evil, Inc."

I don't understand this.  I don't understand the spaces and I don't
understand the %.  Most (all?) message IDs have an @ sign and your posts
certainly do.  I can find the messages only by using (for example)

266426e1.0402230103.5ea4d484@posting.google.com

as the ID.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#3681

On Thursday, August 22, 2013 6:57:03 PM UTC+7, Ben Bacarisse wrote:

> I don't understand this.  I don't understand the spaces and I don't
> understand the %.  Most (all?) message IDs have an @ sign and your posts
> certainly do.  I can find the messages only by using (for example)

I'd try to explain it ... but it could only end
up being an admission of creeping senility dementia.
Let's just nevermind.   :-)

James

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web