[LeetCode] Delete the Middle Node of a Linked List

Problem: 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.

For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node. 

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Approach: The approach is simple. We are going to use fast and slow pointer appoach. The only problem is if slow is at middle, how we are going to delete it. We can maintain a prev pointer or we can make fast start from head.next.next. 

That's all!

Implementation in C#:

With prev node:

    public ListNode DeleteMiddle1(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return null;

        }

        ListNode prev = null, slow = head, fast = head;

        while (fast != null && fast.next != null)

        {

            prev = slow;

            slow = slow.next;

            fast = fast.next;

            if (fast != null)

            {

                fast = fast.next;

            }

        }

        prev.next = prev.next.next;

        return head;

    }

Without prev node:

    public ListNode DeleteMiddle(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;

            if (fast != null)

            {

                fast = fast.next;

            }

        }

        slow.next = slow.next.next;

        return head;

    }

Complexity: O(n)