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

1. Use fast and slow pointer:

  1. //8 ms    6.8 MB
  3. /**
  4.  * Definition for singly-linked list.
  5.  * struct ListNode {
  6.  *     int val;
  7.  *     ListNode *next;
  8.  *     ListNode() : val(0), next(nullptr) {}
  9.  *     ListNode(int x) : val(x), next(nullptr) {}
  10.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     ListNode* middleNode(ListNode* head) {
  16.         ListNode* runner = head;
  17.         ListNode* chaser = head;
  19.         while(runner && runner->next){
  20.             runner = runner->next->next;
  21.             chaser = chaser->next;            
  22.         }
  24.         return chaser;
  26.         //1. runner has next next
  27.         //  runner go
  28.         //  chaser go
  29.         //2. runner has next, has no next next
  30.         //  return chaser->next;
  31.         //3. runner has no next
  32.         //  return chaser;
  33.     }
  34. };

Time Complexity: O(N)
Space Complexity: O(1)