hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Middle of the Linked List


  • Intuition: The hypothesis of the approach below is, if a person can run twice faster as me, then, I will reach the middle point of the road by the time the person reaches the end of the road.


  • Approach:

  1. Declare two nodes namely slow and fast.

  2. The fast node moves twice faster as the slow node.

  3. That is in each iteration we will move the slow to its next node whereas, we will move the fast node to its next node's next node if there are any.

  4. Also, we will check if there is any next node available in case of moving the fast node.

  5. Then we will return the slow node.


  • Time and Space Complexity:

    • Time complexity: O(n)

    • Space complexity: O(1)


Code [C++]

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode() : val(0), next(nullptr) {}

* ListNode(int x) : val(x), next(nullptr) {}

* ListNode(int x, ListNode *next) : val(x), next(next) {}

* };

*/

class Solution {

public:

ListNode* middleNode(ListNode* head) {

ListNode * fast = head, * slow = head;

while(fast->next){

slow = slow->next;

fast = fast->next;

if(fast->next) fast = fast->next;

}

return slow;

}

};