middle of linked list

Question

how to find the middle of the linked list when we are not informed of its size and it must be performed using only one loop and only one pointer.

Answer 1

Node *m,*e,*head; /* head is given */
m=e=head;
while(e) {
  e=e->next;
  if (e) {
    e=e->next;
    m=m->next;
  }
}
/* now m is the middle node */

Sorry, I had to use 2 pointers :)

---

Adding this to your answer, because a minor tweak reduces the number of pointers to 1. I hope you don't mind:

Node m,*e,*head; /* head is given */
e = head;
if (e) m = *e;
while(e) {
  e = e->next;
  if (e) {
    e = e->next;
    m = *(m.next);
  }
}
/* now m is the middle node */

Answer 2

Well, it's sort of a hack, since it's functionally equivalent to 2 loops. But still, it is only 1 loop.

Node* middle(Node* const begin)
{
    Node* current = begin;
    bool size_known = false;
    int size = 0;
    while (true)
    {
        if (!size_known)
        {
            if (current)
            {
                ++size;
                current = current->next;
            }
            else
            {
                current = begin;
                size_known = true;
            }
        }
        else
        {
            if (size <= 1)
                return current;
            current = current->next;
            size -= 2;
        }
    }
}

Answer 3

How about

LinkedList * llist = getLList(); // the linked list
Node * node = llist.head;

while ( node ) {
    node = node.next;
    if ( node ) {
        node  = node.next;
        llist.remove( llist.head );
    }
}
// now llist.head is (er, um... was) the middle node.  
// hope you didn't need the rest of the list.

Answer 4

see my code. it works on my FC9 x86_64 correctly, the function "middle()" is that what you want:

static struct node *middle(struct node *head)
{
        struct node *mid = head;
        int flag = 0;
        while (NULL != head) {
                head = head->next;
                flag = !flag;
                if (flag) {
                        mid = mid->next;
                }
        }
        return mid;
}

EDIT: remove code except the middle().

Answer 5

Iterate over your list using the provided head pointer and increment your one allowed pointer (I assume from your ambiguously-worded question that you're allowed one pointer besides the one that was passed in) once for every two increments of the head pointer.

Node* middle( Node* head )
{
    Node* middle = head;
    while (head != NULL) {
        head = head->next;

        if (head->next != NULL) {
            head = head->next;
            middle = middle->next;
        }
    }
    return middle;
}

There are edge cases ignored here (like what's the middle of a list with an even number of elements).