LeetCode //C - 2095. Delete the Middle Node of a Linked List

2095. Delete the Middle Node of a Linked List

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 ] t h [n / 2]^{th} [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 1:

Example 2:

Example 3:

Constraints:

• The number of nodes in the list is in the range [ 1 , 1 0 5 ] [1, 10^5] [1,105].
• 1 < = N o d e . v a l < = 1 0 5 1 <= Node.val <= 10^5 1<=Node.val<=105

From: LeetCode
Link: 2095. Delete the Middle Node of a Linked List

---

Solution:

Ideas：

This code uses the fast and slow pointer technique to find the middle node. The fast pointer moves two steps at a time, while the slow pointer 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. We then delete the middle node and return the modified list.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* deleteMiddle(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        free(head);
        return NULL;
    }
    
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    struct ListNode *prev = NULL;
    
    // Use the fast and slow pointer approach to find the middle node
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        prev = slow;
        slow = slow->next;
    }
    
    // Delete the middle node
    prev->next = slow->next;
    free(slow);
    
    return head;
}