c++的链表实现；快慢指针找出中间节点（鹅厂）

参考

写一个完整的程序，实现随机生成20个元素的链表,找出中间节点（利用快慢指针）

1、定义结点结构体

struct ListNode
{
   
    int val;
    ListNode* next;
    ListNode() : val(), next() {
   } //无参构造函数
    ListNode(int x) : val(x), next(NULL) {
   } //结构体的有参构造函数
};

2、生成链表

ListNode *GenerateList(int num)
{
   
    ListNode* head=new ListNode(rand()%100);
    ListNode* curNode=head;
    for(int i=1;i<num;++i)
    {
   
        curNode->next=new ListNode(rand()%100);
        curNode=curNode->next;
    }
    return head;
}

3、输出链表
此处注意跳出while循环后，最后一个结点的数据还未输出啊！
我看了很久才发现，(#^.#)

void printList(ListNode* head)
{
   
    ListNode* curNode=head;
    int j=0;
    while(curNode->next!=NULL)
    {
   
        
        cout<<++j<<":"<<curNode->val<<endl;
        curNode=curNode->next;
    }
    cout<<++j<<":"<<curNode->val<<endl;
}

4、快慢指针寻找中间结点

ListNode* findMidNode(ListNode* head)
{
   
    ListNode* fast =head;
    ListNode* slow =head;
    while(fast->next)
    {
   
        if(fast->next->next)
        {
   
            fast=fast->next->next;
            slow=slow->next;
        }
        else fast=fast->next;//为了跳出外层的while循环
    }
    return slow;
}

5、main函数

int main()
{
   
    cout<<"请输入需要创建的链表长度：";
    int num;
    cin >>num;
    ListNode* ListA=GenerateList(num);
    printList(ListA);
    ListNode* MidNode=findMidNode(ListA);
    cout<<"中间节点的数据是："<<MidNode->val;
    return 0;
}

总结：
今晚突发雅兴写篇博客，这还得从一只蝙蝠的故事说起ヾ(^Д*)/
好好利用这段时间学一遍数据结构(｡◕ˇ∀ˇ◕)