COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

• Email
• Follow

```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

```
 0
Reply mayurdjain (29) 4/21/2005 3:20:06 PM

See related articles to this posting

```And how is this on topic for comp.lang.c?

```
 0
Reply GKP1 (83) 4/21/2005 4:37:17 PM

```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

take 2 pointers say
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.

```
 0
Reply ranveerkunal (24) 4/21/2005 7:55:05 PM

```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

```
 0
Reply lndresnick (326) 4/21/2005 8:24:40 PM

```"Darius" <ranveerkunal@gmail.com> wrote in message
>
> 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
> 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

```
 0
Reply mabden2 (464) 5/22/2005 12:21:14 PM

```Mabden wrote:
> "Darius" <ranveerkunal@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
>> 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

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

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

--
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

```
 0
Reply cbfalconer (19194) 5/22/2005 3:14:13 PM

```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;

--
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

```
 0
Reply cbfalconer (19194) 5/22/2005 4:48:19 PM

```"CBFalconer" <cbfalconer@yahoo.com> wrote in message
news:4290B701.40ECEEFA@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>

```
 0
Reply mabden2 (464) 5/26/2005 12:21:06 PM

```Mabden wrote:
> "CBFalconer" <cbfalconer@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>

accurate.

--
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

```
 0
Reply cbfalconer (19194) 5/26/2005 12:51:07 PM

8 Replies
43 Views

Similar Articles

12/4/2013 11:04:40 AM
page loaded in 2783216 ms -1

Similar Artilces:

On Not In List
I have a fundraising database for an organization. Donations come in from current members anad are found by using a combo box. If the member is found, the After Update macro switches to another form where the donation is entered. The problem is that if the donor is not a member, the On Not in List macro won't work for me bringing up a form with a new member number and all the fields that have to be filled out. I guess that the After Update property and On Not In List property conflict. Any workaround? Thanks in advance. news.bellatlantic.net wrote: > The problem is that if the donor is not a member, the On Not in List macro > won't work for me bringing up a form with a new member number and all the > fields that have to be filled out. > > I guess that the After Update property and On Not In List property conflict. > Any workaround? I don't remember that as a conflict. NotInList fires only if you have set LimitToList to True. -- Bas Cost Budde http://www.heuveltop.org/BasCB but the domain is nl On Sun, 08 Feb 2004 16:10:47 GMT, news.bellatlantic.net wrote: > I have a fundraising database for an organization. Donations come in from >

List and sub-list (dependance)
Hello, I have two fields : Field_1 with Principal_list ( AAA, BBB, CCC, other) and Field_2 with Sub_list ( A1,A2,A3 , B1,B2,B3, C1,C2,C3 ....) my question is : when I select AAA in Field_1, it should display only A1,A2,A3 in the Sub_list. So I can only select A1 or A2 or A3. Thank you for giving me the tip. Lambisa Better to split into two tables Table Principal and Table Sub Each table gets two fields Table Principal gets fields: ID_A and Value ID_A should be auto entered, unique Table Sub gets Link and Value When a value is entered the field Link will get the value from ID_A to which it belongs Connect the two tables with a relation Principal::ID_A = Sub::Link. Call the TO connect Create a value list from Principal::ID_A also show Principal::Value On a layout from Principal create a pop-up list with the new value list On same layout make a protal from TO connect and place the field Sub::Link inside it. When you now choose a value from the value list with your pop-up, the calues belonging to it will also show. Just a quick and dirty way, there are several ways to make it better. -- Keep well / Hou je goed Ursus "Lambisa" <

If value is in a list
I have a list of numbers, e.g., (1,3,4,5,8,16,20), and am trying to create a simple IF statement to see if the value is in that list. Is there an easier or more efficient way, than the sample code below, to do it? ===== <script type="text/javascript"> num = 2; list = [1,3,4,5,8,16,20]; if(isInList( num, list )) { alert("It's there!"); } else { alert("It's NOT there!"); } function isInList( num, list ) { // List is an Array() result = false; for(i in list) { if(num == list[i]) { result = true } } return result } </script> On Apr 22, 2:43 pm, Mike <mpea...@gmail.com> wrote: > I have a list of numbers, e.g., (1,3,4,5,8,16,20), and am trying to > create a simple IF statement to see if the value is in that list. Is > there an easier or more efficient way, than the sample code below, to > do it? > > ===== > > <script type="text/javascript"> > num = 2; > list = [1,3,4,5,8,16,20]; > if(isInList( num, list )) { > alert("It's there!");} else { > > alert("It's NOT there!"); > > } > > function isInList

Limit of list
hi, Is there a way to find out the convergence point of a list of numbers? for example if I have {1,2,5,6,8,9,10,11,10,11,12,11,12.. and so on} it will give me something around 10-12 thanks a lot, Guy In article <d79ejm\$lb1\$1@smc.vnet.net>, Guy Israeli <guyi1@netvision.net.il> wrote: > Is there a way to find out the convergence point of a list of numbers? > > for example if I have > > {1,2,5,6,8,9,10,11,10,11,12,11,12.. and so on} > > it will give me something around 10-12 Try SequenceLimit: SequenceLimit[{1,2,5,6,8,9,10,11,10,11,12,11,12}] Also, if your list is entering a cycle there have been previous MathGroup postings on methods for detecting cycles. Cheers, Paul -- Paul Abbott Phone: +61 8 6488 2734 School of Physics, M013 Fax: +61 8 6488 1014 The University of Western Australia (CRICOS Provider No 00126G) AUSTRALIA http://physics.uwa.edu.au/~paul http://InternationalMathematicaSymposium.org/IMS2005/ SequenceLimit. Another COMPLETELY undocumented feature. Just

list equation
Hello to all. Let lst = Tuples[Range[100], 2]; In the previous list appear elements such us {x,y} and {y,x}. (e.g. {3,4} and {4,3}). I want to create a new list with {y,x} dropped (that is, in the new list appears only {3,4} and not {4,3}). I use lstnew = Union[lst, SameTest -> (#1 == Reverse[#2] &)] However it is needed almost 150 sec for this procedure (\$Version->5.2 for Windows) I know that my laptop is too old but I guess there is a more efficient way to create lstnew. Any ideas? Thanks a lot Dimitris Use Sort/@ to sort each element {x,y...; > Let > > lst = Tuples[Range[100], 2]; > > In the previous list appear elements such us {x,y} and {y,x}. (e.g. > {3,4} and {4,3}). > I want to create a new list with {y,x} dropped (that is, in the new > list appears only {3,4} > and not {4,3}). > > I use > > lstnew = Union[lst, SameTest -> (#1 == Reverse[#2] &)] > > However it is needed almost 150 sec for this procedure (\$Version->5.2 > for Windows) > I know that my laptop is too old but I guess there is a more > efficient > way to > create lstnew

List operation
Given two lists In[7]:= x = {a, b, c} y = {A, B, C} I'm looking for the list of pairs z = {{a, A}, {b, B}, {c, C}} Defining the function In[5]:= paarweise[x_, y_, n_] := Table[{x[[i]], y[[i]]}, {i, 1, n}] gives In[6]:= z = paarweise[x, y, 3] Out[6]= {{a, A}, {b, B}, {c, C}} I'm sure there is a more elegant way to get such a list of pairs. Any help is appreciated. Wolfgang Hintze Use Thread[{x,y}] Mariusz >>> Dr. Wolfgang Hintze<weh@snafu.de> 1/16/2004 6:47:50 AM >>> Given two lists In[7]:= x = {a, b, c} y = {A, B, C} I'm looking for the list of pairs z = {{a, A}, {b, B}, {c, C}} Defining the function In[5]:= paarweise[x_, y_, n_] := Table[{x[[i]], y[[i]]}, {i, 1, n}] gives In[6]:= z = paarweise[x, y, 3] Out[6]= {{a, A}, {b, B}, {c, C}} I'm sure there is a more elegant way to get such a list of pairs. Any help is appreciated. Wolfgang Hintze "Dr. Wolfgang Hintze" <weh@snafu.de> wrote in message news:<bu8j16\$au9\$1@smc.vnet.net>... > Given two lists > > In[7]:= > x = {a, b, c} > y = {A, B, C} > > I'm

list() coercion
I have an iterable object. It supports many list-like methods, specifically __len__. These methods are rather expensive (they result in database calls, COUNT(*) to be specific), but cheaper than iterating over the object. Sometimes it is useful to create a list from the iterator, using list(). However, list() seems to call the object's __len__, I imagine to pre-allocate space. This is a problem, as pre-allocation saves much less than is spent doing __len__. Is there a way I can keep this from happening? Maybe something list() tries first that I can make fail. (I notice list() catches any exceptions in __len__ and then will just skip that step) Ian Ian Bicking wrote: > However, list() seems to call the object's > __len__, > > Is there a way I can keep this from happening? Give your object an __iter__ method that returns itself. -- Greg Ewing, Computer Science Dept, University of Canterbury, Christchurch, New Zealand http://www.cosc.canterbury.ac.nz/~greg On Wed, 2003-07-16 at 22:04, Greg Ewing (using news.cis.dfn.de) wrote: > Ian Bicking wrote: > > However, list() seems to call the object's > > __len__, > > >

A List with template
I am studying a java project downloaded from internet, but i can not compile it correctly. one error is that List<string> is not a type, but i have import java.util.List .why? on the other hand, from a book named thinking in java i can not find any info about a List with template. First, it should probably read List<String> and this feature (generics) has been added to Java in version 5. So make sure you're using the correct Java version when compiling. Regards, Bart I don't know if it's a typo but "List<string>" /is/ in fact no valid type... it correctly. > one error is that List<string> is not a type, but i have import > java.util.List .why? > on the other hand, from a book named thinking in java i can not find > any info about a List with template. > thanks alot ��ס���й��ˣ������������� �о������С��� "����" <wangdongyu3d@hotmail.com> д����Ϣ news:1148899308.588895.24200@g10g2000cwb.googlegroups.com... > thanks alot >

list manipulation
Has anyone been able to implement a heapsort with a list? Just some hints :) Thanks in advance. Gerald R. Generoso "Gerald R. Generoso" wrote: > > Has anyone been able to implement a heapsort with a list? > Just some hints :) Why bother? Mergesort will do the job without any fuss. -- Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net) Available for consulting/temporary embedded and systems. <http://cbfalconer.home.att.net> USE worldnet address! On Fri, 05 Dec 2003 20:08:13 GMT, CBFalconer <cbfalconer@yahoo.com> wrote: >"Gerald R. Generoso" wrote: >> >> Has anyone been able to implement a heapsort with a list? >> Just some hints :) > >Why bother? Mergesort will do the job without any fuss. It's called homework. ---------------------------- The reply-to email address is olczyk2002@yahoo.com. This is an address I ignore. To reply via email, remove 2002 and change yahoo to interaccess. ---------------- Thaddeus L. Olczyk, PhD Think twice, code once. There is a difference between *thinking* you know something, and *knowing* you know something. Just because you are learning doesn'

List Managers
Can anyone confirm that list managers such as Majordomo or Mailman use Mprog rather than Mlocal? In article <1070063637.638285@ananke.eclipse.net.uk> John Poltorak <jp@eyup.org> writes: >Can anyone confirm that list managers such as Majordomo or Mailman use >Mprog rather than Mlocal? Your question is a bit strange - neither list managers nor anything else "use" a particular mailer, sendmail does. The local mailer is (obviously) used when sendmail delivers to a local mailbox; the prog mailer is used when sendmail delivers to a script/program, i.e. something that begins with a '|' in aliases or .forward. Most list managers probably have incoming mail processed through this latter mechanism, while the mailer used for outgoing mail depends on the destination - most of the time that is probably one of the SMTP mailers. --Per Hedeland per@hedeland.org