题目
给定一个带有头结点? 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? 之间.
思路一: 单指针
先统计节点个数, 然后从头开始走一半.
代码
时间复杂度: O(n)
空间复杂度: O(1)
- class Solution {
- public:
- ListNode* middleNode(ListNode* head) {
- ListNode *p = head;
- int cnt = 0;
- while (p) {
- ++cnt;
- p = p->next;
- }
- p = head;
- cnt /= 2;
- while (cnt) {
- p = p->next;
- --cnt;
- }
- return p;
- }
- };
思路二: 快慢指针
代码
时间复杂度: O(n)
空间复杂度: O(1)
- class Solution {
- public:
- ListNode* middleNode(ListNode* head) {
- ListNode *fast = head, *slow = head;
- while (fast && fast->next) {
- slow = slow->next;
- fast = fast->next->next;
- }
- return slow;
- }
- };
来源: http://www.bubuko.com/infodetail-3475282.html