由一个题目引出概念
给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:head = [1,2,3,4,5]
输出:[3,4,5]
解释:链表只有一个中间结点,值为 3 。
示例 2:
输入:head = [1,2,3,4,5,6]
输出:[4,5,6]
解法一:朴素解法
这道题最朴素的做法是,先遍历一次,计算链表的长度,进而计算链表中间结点的下标(注意偶数结点的时候,得到的是中间的第二个结点),然后再遍历一次,来到所要求结点的位置。
缺点:必须先遍历完整个链表,然后才可以「干正事」,再遍历到一半,找到中间结点;
在链表的长度很长的时候,这种方法之前的等待会很久。
代码略
解法二:快慢指针法
设置两个指针,一个fast,每次走两步,一个slow,每次走一次,这样当fast走到最后的时候,slow就刚好走到一半
class Solution { public: ListNode* middleNode(ListNode* head) { ListNode* fast; ListNode* slow; while(fast!=nullptr&&fast->next!=nullptr) { fast=fast->next->next; slow=slow->next; } return slow; } };
时间复杂度为O(N),空间复杂度为O(1)
方法三:数组法
这种也是我们最容易想到的方法,把链表存在数组里,然后输出中间的元素
class Solution { public: ListNode* middleNode(ListNode* head) { vector<ListNode*> A = {head}; while (A.back()->next != NULL) A.push_back(A.back()->next); return A[A.size() / 2]; } };
时间复杂度为O(N),空间复杂度为O(N),不如快慢指针法。
总结:
快慢数组法可以节省空间,只用两个指针就可以完成查找任务。