By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,341 Members | 1,399 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,341 IT Pros & Developers. It's quick & easy.

Linked list Question

P: n/a
MJ
Hi
I have a question
I have a singly linked list of 10 elements. I have to find the Nth (Ex
3rd element from the end) element from the end. What are the ways to
do it with less complexity
I have two methods
1. Reverse the linked list and than travese till the Nth location
2. Find the total no of elements in the list and than find the Nth node
postion form the start
both these methods will take complexity more than n + some complexity

other methods are most welcome
MJ

Nov 14 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a
And how is this on topic for comp.lang.c?

Nov 14 '05 #2

P: n/a

MJ wrote:
Hi
I have a question
I have a singly linked list of 10 elements. I have to find the Nth (Ex 3rd element from the end) element from the end. What are the ways to
do it with less complexity
I have two methods
1. Reverse the linked list and than travese till the Nth location
2. Find the total no of elements in the list and than find the Nth node postion form the start
both these methods will take complexity more than n + some complexity

other methods are most welcome
MJ


its OT but i'll answer,
take 2 pointers say
list *ahead, *curr;
i) now move ahead to nth element from head.
ii) put curr on first element.
iii) move both curr and ahead till ahead reaches the end of the list,
now curr points to the element required.

hope it helps.

Nov 14 '05 #3

P: n/a

MJ wrote:
Hi
I have a question
I have a singly linked list of 10 elements. I have to find the Nth (Ex 3rd element from the end) element from the end. What are the ways to
do it with less complexity
I have two methods
1. Reverse the linked list and than travese till the Nth location
2. Find the total no of elements in the list and than find the Nth node postion form the start
both these methods will take complexity more than n + some complexity

other methods are most welcome
MJ


FYI, comp.programming is usually a better place to ask generic
algorithm
questions as opposed to questions about C in particular.

You could put pointers to the list elements into an array and have
random access. Fine for the problem stated above. Not so good if you
are going to change the contents of the list.

-David

Nov 14 '05 #4

P: n/a
"Darius" <ra**********@gmail.com> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...

MJ wrote:
Hi
I have a question
I have a singly linked list of 10 elements. I have to find the Nth

(Ex
3rd element from the end) element from the end. What are the ways to do it with less complexity
I have two methods
1. Reverse the linked list and than travese till the Nth location
2. Find the total no of elements in the list and than find the Nth

node
postion form the start
both these methods will take complexity more than n + some complexity
other methods are most welcome
MJ


its OT but i'll answer,
take 2 pointers say
list *ahead, *curr;
i) now move ahead to nth element from head.
ii) put curr on first element.
iii) move both curr and ahead till ahead reaches the end of the list,
now curr points to the element required.

hope it helps.


It's a common interview question. You just helped some bonehead get a
job he's not qualified for. Thank you for playing.

<rant>It don't understand why you guys help kids cheat on homework, and
"off-shore personnel" steal jobs, when it hurts your neighbors, makes
programmers a commodity item, and takes jobs away from people who can
really perform by giving them to idiots who cheat and steal.</rant>

--
Mabden
Nov 14 '05 #5

P: n/a
Mabden wrote:
"Darius" <ra**********@gmail.com> wrote in message
MJ wrote:

I have a singly linked list of 10 elements. I have to find the
Nth (Ex 3rd element from the end) element from the end. What are
the ways to do it with less complexity
I have two methods
1. Reverse the linked list and than travese till the Nth location
2. Find the total no of elements in the list and than find the
Nth node postion form the start
both these methods will take complexity more than n + some
complexity

other methods are most welcome


its OT but i'll answer,
take 2 pointers say
list *ahead, *curr;
i) now move ahead to nth element from head.
ii) put curr on first element.
iii) move both curr and ahead till ahead reaches the end of the
list, now curr points to the element required.


It's a common interview question. You just helped some bonehead
get a job he's not qualified for. Thank you for playing.

<rant>It don't understand why you guys help kids cheat on homework,
and "off-shore personnel" steal jobs, when it hurts your neighbors,
makes programmers a commodity item, and takes jobs away from people
who can really perform by giving them to idiots who cheat and steal.
</rant>


You're answering something from months ago. However there is
another useful way, and the problem is amusing. Create an array of
pointers of size N, where N is the distance from the end required.
Prefill it with NULLs. Now scan the list, inserting a copy of each
pointer in the array advancing the array index modulo N after
insertion. When you reach the end of the list the current array
position (which would be filled and advanced from if the end had
not been reached) either holds NULL, and the list is shorter than
N, or it holds the pointer to the end-Nth item.

After all that I realize that i am in c.l.c and the whole thing is
OT anyhow. So to bring it on topic I propose some code:

/* assuming suitable definition of node with a next field */
node *findlastbut(unsigned int n, node *root)
{
node *lastn;
unsigned int ix;

n++;
if (!(lastn = malloc(n * sizeof *lastn))) return NULL;
for (ix = 0; ix < n; ix++) lastn[ix] = NULL;
ix = 0;
while (root) {
lastn[ix] = root;
root = root->next;
ix = (ix + 1) % n;
}
root = lastn[ix];
free(lastn);
return root;
} /* findlastbut, untested */

This could actually be an application for C99 flexible arrays.
This minimizes list accesses and never modifies the list.
Therefore, if the malloced memory is available, I claim this is the
optimum algorithm.

For some environments the modulo advance of ix could be
advantageously replaced by:

if (++ix >= n) ix = 0; /* note obfuscative self-healing */

or the while loop could be converted into a for for further
obfuscation.

--
Some informative links:
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html
Nov 14 '05 #6

P: n/a
CBFalconer wrote:
.... snip ...
After all that I realize that i am in c.l.c and the whole thing is
OT anyhow. So to bring it on topic I propose some code:

/* assuming suitable definition of node with a next field */
node *findlastbut(unsigned int n, node *root)
{
node *lastn;
unsigned int ix;

n++;
if (!(lastn = malloc(n * sizeof *lastn))) return NULL;
for (ix = 0; ix < n; ix++) lastn[ix] = NULL;
ix = 0;
while (root) {
lastn[ix] = root;
root = root->next;
ix = (ix + 1) % n;
}
root = lastn[ix];
free(lastn);
return root;
} /* findlastbut, untested */


It is now tested, and the declaration of lastn should be:

node **lastn;

--
Some informative links:
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

Nov 14 '05 #7

P: n/a
"CBFalconer" <cb********@yahoo.com> wrote in message
news:42***************@yahoo.com...
CBFalconer wrote:

... snip ...

It's a common interview question. You just helped some bonehead
get a job he's not qualified for. Thank you for playing.

<rant>It don't understand why you guys help kids cheat on homework,
and "off-shore personnel" steal jobs, when it hurts your neighbors,
makes programmers a commodity item, and takes jobs away from people
who can really perform by giving them to idiots who cheat and steal.
</rant>


Nov 14 '05 #8

P: n/a
Mabden wrote:
"CBFalconer" <cb********@yahoo.com> wrote in message
CBFalconer wrote:

... snip ...

It's a common interview question. You just helped some bonehead
get a job he's not qualified for. Thank you for playing.

<rant>It don't understand why you guys help kids cheat on homework,
and "off-shore personnel" steal jobs, when it hurts your neighbors,
makes programmers a commodity item, and takes jobs away from people
who can really perform by giving them to idiots who cheat and steal.
</rant>


I wrote nothing of the sort. Please keep your attributions
accurate.

--
Some informative links:
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html
Nov 14 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.