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

2024-01-09 08:44:12

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:

在这里插入图片描述

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.

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;
}

文章来源:https://blog.csdn.net/navicheung/article/details/135470596
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。