查找链表的中间结点

查找链表的中间结点

题目：设计一算法查找链表的中间结点。要求该算法的时间复杂度为O(n)，空间复杂度为O(1)。

当看到这个时候想了半天没想出来，时间复杂度是没问题的，但是空间复杂度要达到O(1)还是有一点不好办，然后百度了一下，发现有快指针和慢指针的写法，于是我就进去瞧了瞧，突然惊叹一声“妙啊！”

使用两个指针同时遍历链表，快指针遍历的速度是慢指针的两倍，那么当快指针遍历完整个链表的时候，慢指针恰好位于整个链表的中间部分，那么此刻输出slow->data即为链表中间的元素

代码：

// Created by CAD on 2019/10/14.
#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node* next;
    Node(){next=NULL;}
};
typedef Node* LinkList;
int get_mid(LinkList L)
{
    LinkList slow=L,fast=L;
    for(;fast&&fast->next;)
        slow=slow->next,fast=fast->next->next;
    return slow->data;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    LinkList list1=new Node;
    LinkList p=list1,node;
    p=list1;
    for(int i=1;i<=5;++i)
        node=new Node,node->data=i,p->next=node,p=node;
    cout<<get_mid(list1);
    return 0;
}