企业官网建设流程全解析

一、题目

1.题目描述

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例一：
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
示例二：
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

2.题目链接

https://leetcode.cn/problems/middle-of-the-linked-list

二、题解报告

1.思路分析

方法一：首先遍历一遍单链表，记录链表的长度len，计算中间节点的位置。
用空间换时间：即开辟一个数据ListNode arr[]，记录所有节点，最后返回arr[len/2]的节点即可；
用时间换空间：再次遍历一遍表，遍历到len/2次时返回当前节点记为中间节点。

方法二：利用快慢指针，快指针每次走两步，慢指针每次走一步，所以快指针走的距离为慢指针的两倍，故当快指针遍历到链表末尾时，慢指针指向记为中间节点。(无论是奇数还是偶数，都符合题意)

2.时间复杂度

最坏时间复杂度O(n)。

3.代码详解

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*middleNode(ListNode*head){ListNode*slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}returnslow;}};