Find middle element in a Linked List

Problem Statement: Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Examples:

Input Format: 
( Pointer / Access to the head of a Linked list )
head = [1,2,3,4,5]

Result: [3,4,5]
( As we will return the middle of Linked list the further linked list will be still available )

Explanation: The middle node of the list is node 3 as in the below image.

Input Format: 
Input: head = [1,2,3,4,5,6]

Result: [4,5,6]

Explanation: 
Since the list has two middle nodes with values 3 and 4, we return the second one.

Solution 2: Tortoise-Hare-Approach

Intuition:  Tortoise-Hare-Approach में हम fast ptr को 1 increment और fast ptr को 2 increment  करेंगे इसलिए यदि देखा जाए तो fast ptr fast ptr की तुलना में double travel करेगा | जब fast ptr linked list के end पर होगा तो slow ptr तब तक linked  list के half part को cover  कर लेगी तो slow ptr linked list के middle को point करेगी 

Approach: 

• slow और fast pointers create करे तथा उन्हें head pointer को initialize करे
• Simultaneously slow ptr को 1 step तथा fast ptr को 2 step move कराये जब तक की fast ptr NULL न हो या fast ptr का next NULL न हो |
• जब above condition पूरी हो जाती है तो हम देख सकते है कि slow ptr linked list के middle को point कर रही होगी और इसलिए हम slow ptr को return कर सकते है |

Java Code :

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

C++ Code:

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;
    }
};

Time Complexity: O(N)

Space Complexity: O(1)