leetcode-876. 链表的中间结点解法_leetcod876

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
来源：力扣（LeetCode）
对于这样一个问题，我们很容易就可以想到解决方法，首先通过遍历链表得到表长n，然后再次从表头出发循环n/2次找到中间节点，这样的算法时间复杂度为O(3n/2)。
但是我们还有一个更好的方法，既双指针法来完成这道题目。
我们需要两个快慢指针，慢指针每次移动一位，快指针每次移动两位，而当快指针移动到尾部时，我们的慢指针刚好移动到中间节点，这样的算法时间复杂度为O(n/2)。

        fast = fast->next->next;
        slow = slow->next;
1
2

因为题目要求当存在两个中间节点，既长度为偶数时，需要返回第二个中间节点，所以我们可以这样设置循环条件

    while( fast && fast->next )
    {

        fast = fast->next->next;
        slow = slow->next;
    }
1
2
3
4
5
6

我们不用去判断fast->next->next是否存在，我们可以先让指针移动，然后在下一次循环中判断已经指向后两项的fast是否为空指针，这样就能保证当存在两个中间节点时我们返回的时第二个节点。
完整代码如下：

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast =head;
    struct ListNode* slow =head;
    while( fast && fast->next )
    {

        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11