Find the middle Element of a linked list

The problem, simply

You get the head of a linked list. Give back the middle box.

If the list has an odd number of boxes, there is one middle. If it has an even number, there are two middle boxes, and the usual rule (LeetCode 876 and GeeksforGeeks) is to return the second one. So for 1 2 3 4 5 6 the answer is 4.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count first, then walk.

1. Walk the whole list and count the boxes, n.
2. Start again at the head and take n / 2 steps (whole number division).
3. The box you stand on is the middle. For n = 6 that is 3 steps, landing on 4. For n = 5 it is 2 steps, landing on 3.

class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        for (ListNode p = head; p != null; p = p.next) n++;  // count the boxes
        ListNode curr = head;
        for (int i = 0; i < n / 2; i++) curr = curr.next;     // walk half way
        return curr;
    }
}

How long it takes: one full walk plus half a walk, O(n). Extra room: a counter, O(1). Correct, but it reads the list one and a half times, and some versions of the question say "in one pass".

Way 2: the clever way

Send the kid and the puppy. slow moves one box, fast moves two boxes. When fast cannot take two more steps, slow is at the middle.

1. Put slow and fast on the head.
2. While fast is not null and fast.next is not null: move slow one step and fast two steps.
3. Return slow.

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;          // the kid takes one step
            fast = fast.next.next;     // the puppy takes two
        }
        return slow;                   // the puppy hit the wall, the kid is half way
    }
}

How long it takes: fast crosses the list once, so about n / 2 loop turns, O(n). Extra room: two pointers, O(1). It is one pass, which matters when the list is a stream you can only read once.

Watch out for

• An empty list. head is null, the loop never runs and you return null, which is fine.
• Checking only fast.next != null. When fast itself is null that crashes. Check fast first.
• Moving fast before checking. Always check both fast and fast.next right before the two step jump.

What interviewers ask next

• Return the first middle instead. Change the loop condition as in the trap above, or start fast at head.next.
• Delete the middle node (LeetCode 2095). Keep a prev pointer one box behind slow, then set prev.next = slow.next.
• Is the list a palindrome? Find the middle, reverse the second half, compare the two halves, then reverse it back.
• Split a list into two halves for merge sort. Find the first middle, then cut after it.
• Does the list have a loop? The same two runners: if they ever land on the same box, there is a loop.

Remember this

Grown-up words: the kid and the puppy are the slow and fast pointers, also called the tortoise and hare technique, and walking the list once is a single pass.