middle of linked list

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.

---

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.

---

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

---

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

---

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().

---

We can use skip list in this case:

1) While traversing each node in the Linked List make a skip list of the odd numbered nodes. Time: O(n) Space: O(n/2)

2) Now when you reach the end of the list divide the legnth by 2 and add 1 to get the middle element index.

3) Search for the index in the skip list O(logn) time.

So, Overall Time Complexity of the algorithm would be :

O(n)(1 traversal) + O(logn)(Searching Skip list) = O(n) Space Complexity : O(n/2)

Please reply if this is inefficient....

---

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

---

The C++ way to find the middle of the list since you have tagged c++:

#include <list> 
using namespace std;

using IntegerList = list<int>; 

int main() { 
     IntegerList l; 
     for (int i : {0, 1, 2, 3, 4, 5, 6})
          l.push_back(i * 1); 

     auto m = l.begin(); 
     bool even = false; 
     for(auto &z:l) { 
         if (even) ++m; 
         even = !even; 
     }

     cout << "\nmiddle of the list:" << *m << "\n";
}