Linked List Delete Middle Node

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

Solution

/**
 * 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) {
        
         if (head.next == null) return null;

        ListNode fast = head;
        ListNode slow = new ListNode(0, head);
        while (fast != null && fast.next != null)
        {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

The time complexity of the DeleteMiddle algorithm is O(n), where n is the number of nodes in the linked list. This is because each node in the list is visited exactly once.

The space complexity of the algorithm is O(1). This is because the algorithm only uses a constant amount of space to store the pointers (fast, slow), regardless of the size of the input linked list. The algorithm modifies the input linked list in-place and does not use any additional data structures whose size depends on the input. Hence, the space complexity is constant.