Middle of the Linked List

描述

Given a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

分析

这题也可以用快慢指针来解决，快指针每次走两步，慢指针每次走一步，当快指针走到链表尾部时，慢指针正好走到链表中间。

代码

Java

// TODO

C++

// Middle of the Linked List
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        // 设置两个指针，一个快一个慢
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

Python

# Middle of the Linked List
# 时间复杂度O(n)，空间复杂度O(1)
class Solution:
    def middleNode(self, head):
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

相关题目

• Linked List Cycle
• Linked List Cycle II