给你单链表的头结点 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
思路一:
既然是找中间结点,那么只需要使用“遍历+除2”来解决这个问题,但是也有需要注意的点:也就是 如果元素个数为奇数,则返回中间结点;为偶数,返回第二个中间结点。
class Solution {
public:
ListNode* middleNode(ListNode* head) {
int n = 0;
ListNode* cur = head;
while (cur != nullptr) {
++n;
cur = cur->next;
}
int k = 0;
cur = head;
while (k < n / 2) {
++k;
cur = cur->next;
}
return cur;
}
};
思路二:
但是我们知道,假设有个中间数n,那么2n得到的就是最后一个数,既然这样我们是否可以使用两个速度不同的指针来实现这道题呢?使第二个指针的移动速度是第一个指针的两倍,那么等第二个指针走到最后的时候,第一个指针也就走到中间了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* midp;
// 第二个思路:快慢双指针法
// slow和fast指针都指向头结点
// slow走一步,fast走两步
ListNode *slow, *fast;
slow = fast = head;
// 下述条件必须都满足才能进入循环,并且注意条件的顺序不能改(按照顺序来判断条件,那么反过来会形成短路)
while (fast && fast->next) {
slow = slow->next; //注意元素个数为奇数,则返回中间结点;为偶数,返回第二个中间结点
fast = fast->next->next;
}
return slow;
}