Technical Interview Question

You are given a singly linked list. Write a function to find the middle node of the linked list. If the linked list contains an even number of nodes, return the second middle node.

Implement the following function:

def findMiddleNode(head: ListNode) -> ListNode:
    pass

Input: The input parameter head is the head node of a singly linked list.

Output: Return the middle node of the linked list.

Example

# Example 1
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
middle_node = findMiddleNode(head)
print(middle_node.val)   # Output: 3

# Example 2
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(6)
middle_node = findMiddleNode(head)
print(middle_node.val)   # Output: 4

Constraints

• The number of nodes in the linked list is between 1 and $10^6$.
• The value of each node in the linked list is between -1000 and 1000.
• The linked list will not be empty.

Answer

To find the middle node of a singly linked list, we can use the two-pointer technique. We will initialize two pointers - slow and fast - both initially pointing to the head of the linked list. We can traverse the linked list by moving the slow pointer one step at a time and the fast pointer two steps at a time. By the time the fast pointer reaches the end of the linked list, the slow pointer will be pointing to the middle node.

Here is the step-by-step explanation of the solution:

1. Initialize two pointers, slow and fast, both pointing to the head of the linked list.
2. Traverse the linked list using the two-pointer technique until the fast pointer reaches the end of the linked list.
3. In each iteration, move the slow pointer one step forward and the fast pointer two steps forward.
4. When the fast pointer reaches the end of the linked list, the slow pointer will be pointing to the middle node.
5. Return the middle node.

Below is the implementation of the findMiddleNode function in Python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def findMiddleNode(head: ListNode) -> ListNode:
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

This solution has a time complexity of O(N), where N is the number of nodes in the linked list. We only need to traverse the linked list once using the two-pointer technique.