【每日打卡】 [leetcode]876-链表的中间节点

马谦马谦马谦

615
文章

17
评论

2020 年 3 月 23 日 22:05:13数据结构和算法评论200字数 644阅读 2 分 8 秒阅读模式

来源：力扣（LeetCode）

链接：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 之间。

二、题解

使用快慢指针，快指针每次走 2 步，慢指针每次走 1 步。当快指针指向 null 的时候慢指针就是中间节点。

问题的一个关键点是：如果有两个中间节点，返回第二个。因此要当快指针的下一个节点指向 null 时结束，否则结束条件是快指针的下一个节点是 null 。

三、代码

class Solution {
public:
    ListNode *middleNode(ListNode *head) {
        ListNode *fast, *slow;

        // 链表为空或者只有一个节点
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 快慢指针初始化
        fast = head->next;
        slow = head;

        while (fast != nullptr) {
            // 快慢指针分别走一步
            fast = fast->next;
            slow = slow->next;

            // 快指针在没有到达末尾的时候再走一步
            if (fast) {
                fast = fast->next;
            }
        }

        return slow;
    }
};

class Solution {

public:

ListNode *middleNode(ListNode *head) {

ListNode *fast, *slow;

// 链表为空或者只有一个节点

if (head == nullptr || head->next == nullptr) {

return head;

}

// 快慢指针初始化

fast = head->next;

slow = head;

while (fast != nullptr) {

// 快慢指针分别走一步

fast = fast->next;

slow = slow->next;

// 快指针在没有到达末尾的时候再走一步

if (fast) {

fast = fast->next;

}

return slow;

}

};

测试案例：

TEST(leetcode, demo) {
    int i;
    Solution s;
    ListNode *nodes[6];

    for (i = 0; i < 6; i++) {
        nodes[i] = new ListNode(i);
    }

    // 测试空链表
    EXPECT_EQ(nullptr, s.middleNode(nullptr));
    // 测试只有一个节点的链表
    EXPECT_EQ(nodes[5], s.middleNode(nodes[5]));
    // 测试有两个节点的链表
    EXPECT_EQ(nodes[4], s.middleNode(nodes[4]));
    // 测试 n 个节点的链表，n 为奇数
    EXPECT_EQ(nodes[1], s.middleNode(nodes[1]));
    // 测试 n 个节点的链表，n 为偶数
    EXPECT_EQ(nodes[0], s.middleNode(nodes[0]));
}

int main() {
    ::testing::InitGoogleTest();
    return RUN_ALL_TESTS();
}