链表中间

Question

当我们没有被告知其大小时,如何找到链表的中间,并且必须仅使用一个循环和仅一个指针来执行.

Answer 1

怎么样

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 2

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

对不起,我不得不用2个指针:)

将此添加到您的答案中,因为小调整会将指针数量减少到1.我希望您不要介意:

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