Problem

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

The middle node of a linked list of size n is the ⌊n / 2⌋<sup>th</sup> 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 1:

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.

Example 2:

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.

Example 3:

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.

Solution

Brute Force Approach

1. Calculating the Middle Index:

   • First, we find the length of the linked list. This can be done by traversing the list once and counting the nodes.

   • Next, we calculate the middle index by using n/2 (either the exact middle for odd-length lists or the left-middle for even-length lists).

2. Traversing to the Just-Before Middle Node:

   • We traverse the list again, stopping just before the middle node.

   • This ensures that we can safely delete the middle node without losing the reference to the previous node.

class Solution {
    public int lengthOfLinkedList(ListNode head){
        ListNode temp = head;
        int count = 0;
        while(temp!=null){
            temp = temp.next;
            count += 1;
        }
        return count;
    }

    public ListNode deleteMiddle(ListNode head) {
        if(head == null || head.next==null) return null;
        int n = lengthOfLinkedList(head);

        //Get the before Node of middle
        int middle = n/2;

        ListNode temp = head;
        int count = 1;

        while(count!=middle){
            temp = temp.next;
            count+=1;
        }
        temp.next = temp.next.next;
        return head;
    }
}

Optimal Approach

Storing Previous node

• Tortoise and Hare (link):

  • We use two pointers: a slow pointer (tortoise) and a fast pointer (hare).

  • The slow pointer advances one step at a time, while the fast pointer advances two steps at a time.

  • When the fast pointer reaches the end (or becomes null), the slow pointer will be at the middle node (or the middle-left node for even-length lists).

• Finding the Middle Node:

  • As you traverse the list, keep track of the previous node of the slow pointer.

  • When the fast pointer reaches the end, the slow pointer will be at the middle node, and its previous node will be the one just before the middle.

• Deleting the Middle Node:

  • With the previous node of the slow pointer, you can easily update the next pointer to skip the middle node.

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if(head == null || head.next==null) return null;
        ListNode slow = head;
        ListNode fast = head;

        ListNode prev = slow;

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

        prev.next = slow.next;

        return head;
    }
}

Without Storing Previous Node

1. Delaying the Slow Pointer:

   • Initially, we have both the slow and fast pointers at the head of the linked list.

   • Instead of immediately moving the slow pointer, we let the fast pointer make two steps first.

   • This effectively “delays” the slow pointer by one iteration.

2. Moving Slow and Fast:

   • After the delay, we move the slow pointer one step and the fast pointer two steps.

   • This ensures that the slow pointer ends up exactly before the middle node.

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if(head == null || head.next==null) return null;
        ListNode slow = head;
        ListNode fast = head.next.next;

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

        slow.next = slow.next.next;

        return head;
    }
}