一个单链表，不知道长度，写一个函数快速找到中间节点的位置

/* 假定这个链表只有奇数个节点 */
List *list_middle(List *l)
{
    List *fast;
    List *slow;

    fast = slow = l;

    while (fast != NULL) {
        if (fast->next)
            fast = fast->next->next;
        else
            return slow;
        slow = slow->next;
    }
    return slow;
}

评论

7 楼 elmar 2009-10-27  

恩，我一开始想差了

6 楼 DraculaW 2009-10-26  

elmar 写道

hurricane1026 写道

steven-zhou 写道

/* 假定这个链表只有奇数个节点 */
List *list_middle(List *l)
{
    List *fast;
    List *slow;

    fast = slow = l;

    while (fast != NULL) {
        if (fast->next)
            fast = fast->next->next;
        else
            return slow;
        slow = slow->next;
    }
    return slow;
}

代码太不严谨了。
如果链表有环，你就写了一个死循环。

这也是没办法的事情啊

难道不可以判断一下两个指针什么时候相等么?

5 楼 elmar 2009-10-26  

hurricane1026 写道

steven-zhou 写道

/* 假定这个链表只有奇数个节点 */
List *list_middle(List *l)
{
    List *fast;
    List *slow;

    fast = slow = l;

    while (fast != NULL) {
        if (fast->next)
            fast = fast->next->next;
        else
            return slow;
        slow = slow->next;
    }
    return slow;
}

代码太不严谨了。
如果链表有环，你就写了一个死循环。

这也是没办法的事情啊

4 楼 wantdrink 2009-08-18  

就是拿两根一样的均匀的绳子，一根对折烧，一根就这样烧，对折的烧完了另一根正好烧到一半。

3 楼 myy 2008-12-16  

fast每次跳2步探路，slow每次走1步

2 楼 hurricane1026 2008-12-16  

steven-zhou 写道

/* 假定这个链表只有奇数个节点 */
List *list_middle(List *l)
{
    List *fast;
    List *slow;

    fast = slow = l;

    while (fast != NULL) {
        if (fast->next)
            fast = fast->next->next;
        else
            return slow;
        slow = slow->next;
    }
    return slow;
}

代码太不严谨了。
如果链表有环，你就写了一个死循环。

1 楼 blankyao 2008-12-16  

没看懂...