876. 链表的中间结点

Leetcode题目:链表双指针

给你单链表的头结点 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;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x