Leetcode problem#876: Middle of the Linked List

Problem

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 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

---

We solve this problem by using two pointers. We move the slow pointer by one step and the fast pointer by two steps. When the fast pointer is at the end of the Linked List after traversing, the slow pointer will be in the middle of the list.

Approach

• Initially both pointers point to the first node (Head) of the Linked List.

• Move slow pointer by one step and fast pointer by two steps.

• Repeat the previous step.

There are odd numbers of nodes in the first example. In this case, the fast pointer can't move when the fast pointer.next = null. So, we return the slow pointer, which is the middle element of the Linked List.

And in the second example, there are even numbers of nodes. When the fastPointer = null, it returns the slow pointer, which is the second middle element of the Linked List.

Implementation (Java)

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fastPointer = head;
        ListNode slowPointer = head;

        while(fastPointer!= null && fastPointer.next!= null){
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
        }
        return slowPointer;
    }
}

Complexity Analysis

Time complexity : O(n)
The list has been iterated n times where n is the length of the Linked List.

Space complexity: O(1)
No extra space has been used here.