Linked list Question

Discussion in 'C Programming' started by MJ, Apr 21, 2005.

  1. MJ

    MJ Guest

    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
    MJ, Apr 21, 2005
    #1
    1. Advertising

  2. And how is this on topic for comp.lang.c?
    Gregory Pietsch, Apr 21, 2005
    #2
    1. Advertising

  3. MJ

    Darius Guest

    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.
    Darius, Apr 21, 2005
    #3
  4. MJ

    Guest

    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
    , Apr 21, 2005
    #4
  5. MJ

    Mabden Guest

    "Darius" <> wrote in message
    news:...
    >
    > 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
    Mabden, May 22, 2005
    #5
  6. MJ

    CBFalconer Guest

    Mabden wrote:
    > "Darius" <> 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
    CBFalconer, May 22, 2005
    #6
  7. MJ

    CBFalconer Guest

    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
    CBFalconer, May 22, 2005
    #7
  8. MJ

    Mabden Guest

    "CBFalconer" <> wrote in message
    news:...
    > 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>
    Mabden, May 26, 2005
    #8
  9. MJ

    CBFalconer Guest

    Mabden wrote:
    > "CBFalconer" <> 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
    CBFalconer, May 26, 2005
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    464
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    454
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    491
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    654
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    735
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page