# Deleting the Middle Node of a Linked List Using the Tortoise and Hare Algorithm in TypeScript

### Introduction

In this post, we’ll be solving LeetCode Problem 2095: “Delete the Middle Node of a Linked List.”

The problem statement on LeetCode is:

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

In essence, our goal is to remove the middle node from a singly linked list using an efficient approach that finds the middle without traversing the list multiple times.

To solve it, we’ll employ the Tortoise and Hare (Two-Pointer) algorithm, a technique commonly used for linked list problems involving a slow and a fast pointer. This blog covers the code, essential edge cases, and explains how the two-pointer logic works visually.

If you would prefer a video walkthrough, [**check out my YouTube video here**](https://youtu.be/v9OVEjKngL8?si=Nfds5EqO6nQbRH1k), where I explain the solution step-by-step!

### Problem Breakdown

The task requires us to:

* Traverse the linked list to locate the middle node.
    
* Remove this middle node without needing to re-traverse the entire list.
    

**Constraints:** The linked list will have at least one node.

To tackle this efficiently, we’ll rely on two pointers:

* **Fast Pointer (Hare):** Moves two steps at a time.
    
* **Slow Pointer (Tortoise):** Moves one step at a time.
    

When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

### Step-by-Step Solution Using the Tortoise and Hare Algorithm

#### Step 1: Initialise Pointers

We initialise:

1. `slowPointer` and `fastPointer` both pointing to the head of the linked list.
    
2. `prevPointer` as `null`, to keep track of the node before the slow pointer.
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729907050224/bc12c90c-6595-4ed7-95db-025fc7431ccb.png align="center")

#### Step 2: Traverse the List

With each iteration:

* Update `prevPointer` to point to the current `slowPointer` before it moves forward.
    
* Move `slowPointer` one step forward.
    
* Move `fastPointer` two steps forward.
    

This setup ensures that by the time `fastPointer` reaches the end of the list, `slowPointer` will be at the middle node, and `prevPointer` will be one step behind it.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729907074656/62306be3-e87d-4d21-8464-c15c84bbddf7.png align="center")

#### Step 3: Remove the Middle Node

Once the traversal is complete:

1. **Confirm that** `slowPointer` is at the middle node.
    
2. **Adjust Pointers:** Set `prevPointer.next = slowPointer.next` to "skip" the middle node (the one `slowPointer` is currently pointing to), effectively deleting it from the list.
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1729907849603/1f8f62c9-c44d-4777-8c2e-b21d8055ac4d.png align="center")

#### Step 4: Edge Case - Single Node List

If the list has only one node, `fastPointer` won’t be able to move two steps. In this case:

* Simply return `null` as removing the middle node from a single-node list leaves the list empty.
    

### Code Implementation in TypeScript

Here’s how the solution looks in TypeScript:

```typescript
function deleteMiddle(head: ListNode | null): ListNode | null {
    if (!head.next) {
        return null;
    }

    let slowPointer = head;
    let fastPointer = head;
    let prevPointer = null;

    while (fastPointer && fastPointer.next) {
        prevPointer = slowPointer;
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
    }

    if (prevPointer) {
        prevPointer.next = slowPointer.next;
    }

    return head;
};
```

### Explanation of the Code

* **Edge Case Handling:** The first check ensures that if the list has only one node (or none), it returns `null`.
    
* **Traversing the List:** The `while` loop moves `fastPointer` by two steps and `slowPointer` by one step. At the same time, `prevPointer` updates to stay one step behind `slowPointer`.
    
* **Node Deletion:** After the loop, `prevPointer.next` is set to `slowPointer.next`, effectively removing the middle node from the list.
    

### Complexity Analysis

* **Time Complexity:** O(n) because we’re traversing the list with the two pointers just once.
    
* **Space Complexity:** O(1) as no additional space is used beyond the three pointers.
    

### Edge Cases and Additional Considerations

1. **Single Node List:** As mentioned, returning `null` when there’s only one node in the list.
    
2. **Two Node List:** After removing the middle node, the list should contain just one node.
    
3. **Odd vs. Even Length Lists:** For an odd-length list, the exact middle node is removed. For an even-length list, the second of the two central nodes is considered the middle.
    

### Conclusion

The Tortoise and Hare algorithm provides an efficient solution to this problem by requiring only a single traversal to locate and delete the middle node. This approach is also valuable for other linked list problems, such as detecting cycles or identifying the start of a loop.

Mastering this algorithm will deepen your understanding of linked list problem-solving, a skill that often proves valuable in coding interviews.