2095. Delete the Middle Node of a Linked List

Time: O(n)

Space: O(1)

Problem Overview

The middle node of a linked list is found with the classic slow/fast pointer technique: when fast reaches the end, slow sits on the node to remove.

Intuition

The middle node of a linked list is found with the classic slow/fast pointer technique: when fast reaches the end, slow sits on the node to remove. A dummy node before the head handles the edge case where the middle is the first node. If the target has a successor, copy its value and skip the next node; otherwise unlink the tail through the tracked predecessor.

Algorithm

1Create dummy start pointing to head; initialize slow, fast, and prev at head.
2While fast and fast.next exist, advance prev to slow, slow by one, and fast by two.
3If slow.next is not null, copy slow.next.val into slow and set slow.next = slow.next.next.
4Else if slow is the head node, set start.next = null.
5Else set prev.next = null to remove the tail middle.
6Return start.next.

Example Walkthrough

Input: head = [1, 3, 4, 7, 1, 2, 6]

1.Seven nodes: slow/fast stops with slow on node 4 (the middle).
2.slow.next exists, so copy 7 into slow and skip the next node.
3.Result list is 1 -> 3 -> 4 -> 1 -> 2 -> 6.

Output: [1, 3, 4, 1, 2, 6]

Common Pitfalls

•Use a dummy node so deleting the first/middle node does not lose the list head.
•Track prev during the slow/fast walk for tail-deletion cases.
•When slow.next is null, do not copy-delete; unlink with prev or dummy instead.

2095.cs

// Approach: Use slow/fast pointers to find the middle node, with a dummy head for the case
// where the middle is the first node. Delete by copying the next value or unlinking the tail.
// Time: O(n) Space: O(1)

//Definition for singly-linked list.
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode DeleteMiddle(ListNode head)
    {
        ListNode start = new ListNode(0);
        start.next = head;
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = head;

        while (fast != null && fast.next != null)
        {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        if (slow.next != null)
        {
            slow.val = slow.next.val;
            slow.next = slow.next.next;
        }
        else
        {
            if (slow.val == head.val)
                start.next = null;
            else
                prev.next = null;
        }

        return start.next;
    }
}

Was this solution helpful?