寻找一个单向链表的中项，如果存在两个则返回前一个，请给出算法

[问答题]

寻找一个单向链表的中项，如果存在两个则返回前一个，请给出算法描述并给出代码实现。

查看答案及解析

推荐

comtjz

两个结点指针，一个指针走一步，一个指针走两步，当走两步的指针到终点时，走一步的指针即中间结点。

ListNode *findMiddleNode(ListNode *pHead)
{
    if (NULL == pHead)
        return pHead;

    ListNode *pNodeOne = pHead;
    ListNode *pNodeTwo = pHead;
    while (pNodeTwo)
    {
        pNodeTwo = pNodeTwo->m_pNext;
        if (pNodeTwo)
        {
            pNodeOne = pNodeOne->m_pNext;
            pNodeTwo = pNodeTwo->m_pNext;
        }
        else
        {
            break;
        }
    }

    return pNodeOne;
}

编辑于 2015-01-14 23:26:37 回复(4)

0Ver1

两个指针，p1走一步，p2走两步，p2到终点时p1正好为中项

Lnode * SearchMid(LinkList *L){
    LNode *p1,*p2;
    p1 = p2 = L;
    while(p2->link!=NULL && p2->link->link!=NULL){
        p1 = p1->link;
        p2 = p2->link->link;  
    }
    return p1;
}

发表于 2017-07-22 15:20:39 回复(1)

叫我大头

如果PHP怎么实现，PHP没有指针概念。

不知道这样可以吗:找出链表长度，再遍历

发表于 2017-08-04 08:57:31 回复(0)

chng

两个指针从头走，一个走两步一个走一步，直到前面的指针q为空或者q->next为空退出。

退出时：

如果q为空，说明一共有偶数个节点，返回后面的指针p的前驱；否则如果q->next为空，则有奇数个节点，而p指向的正是中间点。

发表于 2015-03-12 13:12:03 回复(0)

飞20180209221594

两个指针，p1走1，p2走2，当p2!=null 并且p2->next!=null时，才执行{p1=p1->next;p2=p2->next->next;}

编辑于 2020-02-19 17:52:53 回复(0)

秒速__五厘米

快慢指针或者递归都可以解决就是不知道哪个更好

发表于 2018-01-23 10:08:05 回复(0)

等待一朵花开

使用两个指针，都指向表头，一个慢指针：每次向后移动一位，一个快指针：每次向后移动两位。当快指针指向空时，结束，输出慢指针指向的节点即为中项，时间复杂度为n/2

发表于 2016-07-13 11:36:07 回复(0)

小雨落梧桐

思路:单链表返回中点. 快慢指针,pSLow一次运行1步,pFast一次跑两步,pFast指向结尾时候,此时pSlow正好是中点

typedef int ElemType;
struct sNode
{
    ElemType data;
    sNode *next;
};

sNode* FindListMiddleNode(sNode* HL)//带表头附加结点
{
    if(!HL || !HL->next)//如果HL为空或者它根本没有数据结点,返回NULL
        return NULL;
    sNode *pSlow, *pFast; 
    pSlow = HL->next;
    pFast = HL->next->next;
    while(pFast && pFast->next)
    {
        pSlow = pSlow->next;
        pFast = pFast->next->next;//一次两步
    }
    return pSlow;//返回中点
}

编辑于 2015-04-28 11:07:12 回复(1)

念润

#include <iostream>
    using namespace std;

    struct ListNode{
        int val;
        ListNode *next;
        ListNode(int x):val(x),next(nullptr){}
    };

    ListNode* ListMedian(ListNode* head){
        if(head == nullptr){
            return nullptr;
        }//if
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast->next != nullptr && fast->next->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }//while
        return slow;
    }

    int main(){
        int num[] = {1,2,3,4,5};
        ListNode *head = new ListNode(0);
        ListNode *p = head,*node;
        for(int i = 0;i < 5;++i){
            node = new ListNode(num[i]);
            p->next = node;
            p = p->next;
        }//for
        node = ListMedian(head->next);
        if(node != nullptr){
            cout<<node->val<<endl;
        }//if
    }

发表于 2015-03-30 12:00:31 回复(0)