地址:https://leetcode-cn.com/problems/middle-of-the-linked-list/

题目

给定一个带有头结点 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 之间。

解题思路

思路很简单,定义两个指针并且都初始化为指向头结点,然后 cur 指针遍历整个链表,cur 每移动两个结点,mid 指针就往后移动一个结点,这样 mid 就始终是从 headcur 的中间结点,直到 cur 遍历完整个链表,则 mid 所指向的结点即整个链表的中间结点。

需要注意头结点本就是中间结点,往后移动一个结点的时候,就应该将 mid 指向第二个结点。

👉🏻更好一点的办法是用 step 记录节点数,偶数个结点的时候 mid 就往后移动一个结点,这样就不用对头结点特殊处理。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* mid = head;//始终指向中间结点
        ListNode* cur = head;//当前结点
        int step = 1;//cur每隔一步往后移一位
        while (cur != NULL) {
            if (step == 0) {
                mid = mid->next;
                step = 1;
                cur = cur->next;
                continue;
            }
            cur = cur->next;
            step--;
        }
        return mid;
    }
};

更好一点的办法

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* mid = head;//始终指向中间结点
        ListNode* cur = head;//当前结点
        int step = 1;//结点数为偶数的时候指针mid往后移一位
        while (cur != NULL) {
            if (step % 2 == 0)
                mid = mid->next;
            cur = cur->next;
            step++;
        }
        return mid;
    }
};


Leetcode      Leetcode C++

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!