Linked List

[source]

function that would: return the 5th element from the end in a singly
linked list of integers, in one pass, and then provide a set of test
cases
against that function.

And please dont think this is my homework.
Can anybody simple tell me how this can be done. I am preparing for an
interview and wanted to know how to go about implementing this.
Or atleast tell me where I can find few examples on traversing Lists.
Even if I can get any good resources which explains lists properly my
job will be done.

[Siemel Naran]

Re: Linked List

"source" <subscrib_77@ho tmail.com> wrote in message
[color=blue]
> function that would: return the 5th element from the end in a singly
> linked list of integers, in one pass, and then provide a set of test
> cases
> against that function.[/color]

Show us your best effort so far. Also try to write a function that finds
the 5th element in a container matching a certain condition (for example,
the element is >10).

[Siemel Naran]

Re: Linked List

"source" <subscrib_77@ho tmail.com> wrote in message
[color=blue]
> function that would: return the 5th element from the end in a singly
> linked list of integers, in one pass, and then provide a set of test
> cases
> against that function.[/color]

Show us your best effort so far. Also try to write a function that finds
the 5th element in a container matching a certain condition (for example,
the element is >10).

[osmium]

Re: Linked List

source writes:
[color=blue]
> function that would: return the 5th element from the end in a singly
> linked list of integers, in one pass, and then provide a set of test
> cases
> against that function.
>
> And please dont think this is my homework.
> Can anybody simple tell me how this can be done. I am preparing for an
> interview and wanted to know how to go about implementing this.
> Or atleast tell me where I can find few examples on traversing Lists.
> Even if I can get any good resources which explains lists properly my
> job will be done.[/color]

If I understand the question, it can't be done; at least on a bare bones
linked list. You will have to count the elements so you can subtract five
from that. And then traverse the list again, which would be easiest from
the head end. I call that two passes, not one that you asked for. My
default meaning for end is the far end; I call the other end the beginning.

For test cases, test for within range, each valid boundary and one beyond
each valid boundary. Valid because numbering might start with zero or one.

[osmium]

Re: Linked List

source writes:
[color=blue]
> function that would: return the 5th element from the end in a singly
> linked list of integers, in one pass, and then provide a set of test
> cases
> against that function.
>
> And please dont think this is my homework.
> Can anybody simple tell me how this can be done. I am preparing for an
> interview and wanted to know how to go about implementing this.
> Or atleast tell me where I can find few examples on traversing Lists.
> Even if I can get any good resources which explains lists properly my
> job will be done.[/color]

If I understand the question, it can't be done; at least on a bare bones
linked list. You will have to count the elements so you can subtract five
from that. And then traverse the list again, which would be easiest from
the head end. I call that two passes, not one that you asked for. My
default meaning for end is the far end; I call the other end the beginning.

For test cases, test for within range, each valid boundary and one beyond
each valid boundary. Valid because numbering might start with zero or one.

[Siemel Naran]

Re: Linked List

"osmium" <r124c4u102@com cast.net> wrote in message news:c4pnvn$2kb bqu$1@ID-
[color=blue][color=green]
> > function that would: return the 5th element from the end in a singly
> > linked list of integers, in one pass, and then provide a set of test
> > cases against that function.[/color][/color]
[color=blue]
> If I understand the question, it can't be done; at least on a bare bones
> linked list. You will have to count the elements so you can subtract five
> from that. And then traverse the list again, which would be easiest from
> the head end. I call that two passes, not one that you asked for. My
> default meaning for end is the far end; I call the other end the[/color]
beginning.

You can do it in one pass. The first way to implement it could actually be
slower than the 2 pass method, and the second way would probably be faster.

[color=blue]
> For test cases, test for within range, each valid boundary and one beyond
> each valid boundary. Valid because numbering might start with zero or[/color]
one.

I'd say the empty list, list of 1 element, list of 5 elements, list of >5
elements.

[Siemel Naran]

Re: Linked List

"osmium" <r124c4u102@com cast.net> wrote in message news:c4pnvn$2kb bqu$1@ID-
[color=blue][color=green]
> > function that would: return the 5th element from the end in a singly
> > linked list of integers, in one pass, and then provide a set of test
> > cases against that function.[/color][/color]
[color=blue]
> If I understand the question, it can't be done; at least on a bare bones
> linked list. You will have to count the elements so you can subtract five
> from that. And then traverse the list again, which would be easiest from
> the head end. I call that two passes, not one that you asked for. My
> default meaning for end is the far end; I call the other end the[/color]
beginning.

You can do it in one pass. The first way to implement it could actually be
slower than the 2 pass method, and the second way would probably be faster.

[color=blue]
> For test cases, test for within range, each valid boundary and one beyond
> each valid boundary. Valid because numbering might start with zero or[/color]
one.

I'd say the empty list, list of 1 element, list of 5 elements, list of >5
elements.

[David Harmon]

Re: Linked List

On 4 Apr 2004 12:05:51 -0700 in comp.lang.c++, subscrib_77@hot mail.com
(source) wrote,[color=blue]
>function that would: return the 5th element from the end in a singly
>linked list of integers, in one pass, and then provide a set of test
>cases
>against that function.[/color]

This sentence no verb.

What I consider the usual approach to that kind of thing is what I call
a "following pointer". That is, you have two iterators, one points to
where you are looking in the list and the other five items behind it.
You advance both of them at the same time. When you get to what you
were looking for (in this case, the end) the "following" iterator points
to what you wanted.

No doubt you can write the C++ code based on that.

[David Harmon]

Re: Linked List

On 4 Apr 2004 12:05:51 -0700 in comp.lang.c++, subscrib_77@hot mail.com
(source) wrote,[color=blue]
>function that would: return the 5th element from the end in a singly
>linked list of integers, in one pass, and then provide a set of test
>cases
>against that function.[/color]

This sentence no verb.

What I consider the usual approach to that kind of thing is what I call
a "following pointer". That is, you have two iterators, one points to
where you are looking in the list and the other five items behind it.
You advance both of them at the same time. When you get to what you
were looking for (in this case, the end) the "following" iterator points
to what you wanted.

No doubt you can write the C++ code based on that.

[Pete]

Re: Linked List

source wrote:[color=blue]
> function that would: return the 5th element from the end in a singly
> linked list of integers, in one pass, and then provide a set of test
> cases
> against that function.
>
> And please dont think this is my homework.
> Can anybody simple tell me how this can be done. I am preparing for an
> interview and wanted to know how to go about implementing this.
> Or atleast tell me where I can find few examples on traversing Lists.
> Even if I can get any good resources which explains lists properly my
> job will be done.[/color]

P-code, and without error checking (assumes list is at least 5 long):

node* node = yourfirstnode;
node* node5 = node->next->next->next->next;

for(;;)
{
if(node5->next == 0)
{
return node->val;
}
node = node->next;
node5 = node5->next;
}

- Pete

[Pete]

Re: Linked List

source wrote:[color=blue]
> function that would: return the 5th element from the end in a singly
> linked list of integers, in one pass, and then provide a set of test
> cases
> against that function.
>
> And please dont think this is my homework.
> Can anybody simple tell me how this can be done. I am preparing for an
> interview and wanted to know how to go about implementing this.
> Or atleast tell me where I can find few examples on traversing Lists.
> Even if I can get any good resources which explains lists properly my
> job will be done.[/color]

P-code, and without error checking (assumes list is at least 5 long):

node* node = yourfirstnode;
node* node5 = node->next->next->next->next;

for(;;)
{
if(node5->next == 0)
{
return node->val;
}
node = node->next;
node5 = node5->next;
}

- Pete

[Kevin Goodsell]

Re: Linked List

osmium wrote:
[color=blue]
> source writes:
>
>[color=green]
>>function that would: return the 5th element from the end in a singly
>>linked list of integers, in one pass,[/color]
>
>
> If I understand the question, it can't be done; at least on a bare bones
> linked list. You will have to count the elements so you can subtract five
> from that. And then traverse the list again, which would be easiest from
> the head end. I call that two passes, not one that you asked for. My
> default meaning for end is the far end; I call the other end the beginning.
>[/color]

Keep two pointers. Begin traversing the list with the first. 5 elements
in, begin traversing with the second. Once the first reaches the end,
the second will be 5 elements from the end.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[Kevin Goodsell]

Re: Linked List

osmium wrote:
[color=blue]
> source writes:
>
>[color=green]
>>function that would: return the 5th element from the end in a singly
>>linked list of integers, in one pass,[/color]
>
>
> If I understand the question, it can't be done; at least on a bare bones
> linked list. You will have to count the elements so you can subtract five
> from that. And then traverse the list again, which would be easiest from
> the head end. I call that two passes, not one that you asked for. My
> default meaning for end is the far end; I call the other end the beginning.
>[/color]

Keep two pointers. Begin traversing the list with the first. 5 elements
in, begin traversing with the second. Once the first reaches the end,
the second will be 5 elements from the end.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[Siemel Naran]

Re: Linked List

"Pete" <x@x.x> wrote in message news:yKZbc.1487 0
[color=blue]
> node* node = yourfirstnode;
> node* node5 = node->next->next->next->next;[/color]

What happens on a list of 0 to 4 elements?

[Siemel Naran]

Re: Linked List

"Pete" <x@x.x> wrote in message news:yKZbc.1487 0
[color=blue]
> node* node = yourfirstnode;
> node* node5 = node->next->next->next->next;[/color]

What happens on a list of 0 to 4 elements?