Middle Of The Linked List - Leetcode Solution

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.

Example: Input: head = [1,2,3,4,5] Output: [3,4,5]

Solution:

To solve the problem, we can use two pointers, a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the linked list, the slow pointer would have moved to the middle node.

Algorithm:

1. Initialize the slow pointer and fast pointer to the head of the linked list.
2. Traverse the linked list using the fast pointer until it reaches the end of the list.
3. During each iteration, move the slow pointer one step and the fast pointer two steps.
4. When the fast pointer reaches the end of the linked list, the slow pointer will be pointing at the middle node.
5. If there are even number of nodes, the slow pointer should point to the second middle node.
6. Return the middle node pointed by the slow pointer.

Pseudo Code:

def middleNode(head: ListNode) -> ListNode: slow = head fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

return slow

Code Explanation:

The above code defines the function middleNode which accepts the head of a singly linked list as input and returns the middle node of the linked list.

We initialize two pointers, slow and fast, to the head of the linked list. We then traverse the linked list using the fast pointer until it reaches the end of the list. During each iteration, we move the slow pointer one step and the fast pointer two steps. When the fast pointer reaches the end of the linked list, the slow pointer will be pointing at the middle node. If there are even number of nodes, the slow pointer should point to the second middle node. We then return the middle node pointed by the slow pointer.

Time Complexity:

The time complexity of the above algorithm is O(n/2) which can be simplified to O(n), where n is the number of nodes in the linked list. This is because, in the worst case scenario, we will have to traverse half of the linked list to get to the middle node.

Space Complexity:

The space complexity of the above algorithm is O(1) because we are not using any extra space.

1