Topics › Linked List › Medium Problems of LL

Delete the middle node in LL

Medium TUF ID 619 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the head of a singly linked list with n nodes. Delete the middle node, defined as the node at 0-based index floor(n / 2), and return the head of the modified list. For n = 1, 2, 3, 4, 5 the middle indices are 0, 1, 1, 2, 2. If the list has a single node, deleting its middle leaves an empty list, so return null.

Constraints: 1 ≤ n ≤ 10^5 in the LeetCode version (the Java code also accepts an empty list and returns null), values fit in a 32-bit signed integer.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

head = 1 -> 3 -> 4 -> 7 -> 1 -> 2 -> 6     (n = 7, middle index 3)
answer = 1 -> 3 -> 4 -> 1 -> 2 -> 6        // the 7 is removed

Example 2

head = 1 -> 2 -> 3 -> 4                    (n = 4, middle index 2)
answer = 1 -> 2 -> 4                       // for even n the second of the two middle nodes goes

Example 3

head = 2 -> 1                              (n = 2, middle index 1)
answer = 2

Approach 1: Brute force, count then delete

Intuition. Once we know n, the middle is at index n / 2 (integer division). To unlink it we need its predecessor, the node at index n / 2 - 1. So count the nodes in one pass, walk n / 2 - 1 steps in a second pass, and bypass the next node.

Algorithm.

1. If the list has 0 or 1 nodes, return null.
2. Count the nodes to get n.
3. Walk n / 2 - 1 steps from head; the pointer is now on the predecessor of the middle.
4. Set predecessor.next = predecessor.next.next and return head.

static ListNode bruteForce(ListNode head) {
    if (head == null || head.next == null) return null;   // 0 or 1 node: deleting the middle leaves nothing
    int n = 0;
    for (ListNode t = head; t != null; t = t.next) n++;
    ListNode t = head;
    for (int i = 0; i < n / 2 - 1; i++) t = t.next;       // stop on the node just before the middle
    t.next = t.next.next;
    return head;
}

Complexity. Time O(n): a full pass to count and about half a pass to reach the predecessor. Space O(1).

For n = 2, n / 2 - 1 = 0, so the predecessor is the head and the second node is removed, which matches the definition. The check for fewer than two nodes at the top guarantees n / 2 - 1 ≥ 0 afterwards.

Approach 2: Optimal, slow and fast pointers with a head start

Intuition. The slow and fast pointer trick finds the middle in one pass: when fast (moving two nodes per step) reaches the end, slow (moving one node per step) is at the middle. But we need the node before the middle in order to delete it. Rather than tracking an extra prev pointer, give fast a head start of two nodes. Then, when fast runs out, slow is one node short of the middle, exactly where we need it.

To see why the head start works, note that with both pointers starting at head, slow ends at index floor(n / 2). Starting fast two nodes further is equivalent to running the standard version on a list that is two nodes shorter, which stops slow at index floor((n - 2) / 2) = floor(n / 2) - 1.

Algorithm.

1. If the list has 0 or 1 nodes, return null.
2. Set slow = head and fast = head.next.next.
3. While fast and fast.next are non-null: slow = slow.next, fast = fast.next.next.
4. slow.next is the middle; set slow.next = slow.next.next and return head.

static ListNode optimal(ListNode head) {
    if (head == null || head.next == null) return null;
    ListNode slow = head, fast = head.next.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    slow.next = slow.next.next;          // slow.next is the middle node
    return head;
}

Dry run on 1 -> 2 -> 3 -> 4 -> 5 -> 6 (n = 6, middle index 3, value 4):

On 1 -> 2 (n = 2): fast = head.next.next = null, the loop does not run, and slow.next = null removes the second node. On 1 -> 2 -> 3: fast starts on 3, whose next is null, so again the loop does not run and the 2 is removed.

Complexity. Time O(n): fast walks the list once; slow walks half of it. Space O(1): two pointers.

Both approaches are tested against an array reference that drops index n / 2, on lists of length 0 through 7 and on lists of 100 000 and 100 001 nodes.

Edge cases and pitfalls

• Single node. The middle is the only node; return null. Without the early check, head.next.next would throw a NullPointerException.
• Empty list. Not part of the LeetCode constraints, but the same early check returns null safely.
• Two nodes. The middle is index 1 (the second node); fast starts as null.
• Even length. The definition picks the second of the two central nodes (floor(n / 2)), not the first. Check the problem text; some variants delete the first.
• Deleting the node you are standing on. A singly linked node cannot remove itself. Always stop on the predecessor, which is why fast gets a head start here instead of tracking prev.
• Loop condition. Use fast != null && fast.next != null; dropping either half dereferences null on some length.
• Values versus structure. Nothing here depends on values; a list of equal values is tested to make sure the position logic alone decides.

Related problems

• Middle of a LinkedList [TortoiseHare Method] finds the middle without deleting it.
• Remove Nth node from the back of the LL is another “stop on the predecessor” deletion with two pointers.
• Deletion of the head of LL covers the only node that has no predecessor.
• Check if LL is palindrome or not also relies on finding the middle in one pass.