Linked list problem


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: Linked list problem

  1. #1
    Join Date
    Mar 2005
    Posts
    1

    Smile Linked list problem

    quest: find midlle element of a linked list in one traversal.
    I have one soln. but i dnt think that goes in one traversal
    it is
    first=list;
    sec=list;
    while(sec->next != NULL)
    {
    first=first->next;
    sec=sec->next->next;
    }
    cout<<first->val;

    As when we are checking sec->next we are accessing linked list . and by incrementing first=first->next we are also traversing LL . so its not parrallel working not a single traversal

    Any other soln.

  2. #2
    Join Date
    Jan 2005
    Location
    UK
    Posts
    604
    Hi,

    do you mean the n-th element in a list of length 2*n-1? the solution could be something like:
    set pointer p1 to the beginning of the list
    set pointer p2 to the end of the list
    iteratively set p1 to p1->next und p2 to p2->prev until p1 == p2
    Tat won't work of course, if the number of elements in your list is even, but it would work in 1 iteration.
    Cheers,

    Dieter

  3. #3
    Join Date
    Dec 2003
    Posts
    3,366
    its trivial for a doubly linked list, but for a singly linked list?
    You need to know how many you have, but if you don't maintain that, how to do it?

    start two pointers at 'head'
    now you just increment two to one. Every time you advance the main pointer forward two nodes, advance the other pointer one node. When the main pointer hits 'null', your other pointer points to the element in the middle. (n/2 rounded down for even lists)

    The problem is unrealistic because if you needed the middle element, you would maintain a pointer to it or a count of the nodes so you could just go 1/2 way. Linked lists are so slow... I have not used one since school...
    Last edited by jonnin; 03-31-2005 at 05:31 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center