Leetcode # 876. Middle of the Linked List

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

Solution

*fast 的速度是 *slow 的兩倍

Time Complexity: O(len(head))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

C++ 版

class Solution {
public:
  ListNode* middleNode(ListNode* head) {
    ListNode *fast = head, *slow = head;
    while(fast && fast->next){
      fast = fast->next;
      if(fast)fast = fast->next;

      slow = slow->next;
    }
    return slow;
  }
};

Python 版

class Solution:
  def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    step = 0
    fast = slow = head
    while fast:
      fast = fast.next
      if step % 2 == 1:
        slow = slow.next
      step += 1

    return slow

Last Updated on 2023/08/16 by A1go