https://www.educoder.net/problems/35meyxwn4a9j/oj/9ntpk43e

上面是题目原题:

题目描述

补充函数 fun。

line 链表是一个有序链表，现请你找出此链表的中间节点，
将此节点的值返回。

如果链表节点数是偶数，则取中间靠左的节点的值。
输入格式

本题只需关注 fun 函数，现解释函数参数意义：
line: 一个有序链表，有空数据的头结点。
输出格式

本题只需关注 fun 函数，现解释函数返回值意义：
返回中间节点的值，整数类型。
输入输出样例
输入1

1 2 3 4 5
输出1

3
输入2

1 2 3 4
输出2

2

解题

刚开始想的,是死方法:

int fun(struct Node* line)
{
	//start
    int len = 0;
    struct Node* temp = line;
    while(temp != NULL) {
        len++;
        temp = temp->next;
    }
    temp = line;
    for(int i = 0;i<len/2;i++) {
        temp = temp->next;
    }
    return temp->value;
    //end

}

倒是也AC了,但是看了一下题解,发现有人用的快慢指针

int fun(struct Node* line)
{
    //start
    struct Node* slow=line->next;
    struct Node* quick=slow->next;
    while(quick!=NULL && quick->next!=NULL){
        slow=slow->next;
        quick=quick->next->next;
    }
    return slow->value;
    //end

}

原理就是一个慢指针指在前面,快指针指在慢指针后面,快指针每次前进两个结点,满指针每次前进一个结点,这样当快指针超出范围的时候,正好就是慢指针指向中间值的时候