给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:head = [1,2,3,4,5] 输出:[3,4,5] 解释:链表只有一个中间结点,值为 3 。
示例 2:
输入:head = [1,2,3,4,5,6] 输出:[4,5,6] 解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。
提示:
- 链表的结点数范围是
[1, 100] 1 <= Node.val <= 100
解题思路
双指针
话是这么说,但还是先用暴力直接写看一下。
/**
* 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) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode*cur=head;
int len=0;
while(cur!=NULL)
{
len++;
cur=cur->next;
}
cur=head;
len/=2;
while(len--)
{
cur=cur->next;
}
return cur;
}
};
接下来看看双指针。快指针每次走2步,慢指针每次走1步。如果总长度len为偶数,那快指针走到NULL的时候走了n/2次,共走了n的距离;慢指针则同样走了n/2次,共走了n/2的距离。如果长度len为奇数,那快指针走到尾节点的时候走了n-1/2次,共走了n-1的距离;慢指针同样走了n-1/2次,共走了n-1/2的距离。
/**
* 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) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode*fast=head;
ListNode*slow=head;
while(fast!=NULL&&fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
};