###### tags: `Leetcode` `medium` `list` `pointer` `python` `c++`

# 2095. Delete the Middle Node of a Linked List

## [題目連結:] https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/

## 題目:
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.


## 解題想法:
* 此題為刪除linked-list: 中間的node
* 奇數list: 為中間點
* 偶數list: 中間兩點偏右的那點

* 使用two-pointer:
* fast=head: 每次移動兩步
* slow=head: 每次移動一步
* 額外需要一個pre紀錄slow的前一點
* while fast and fast.next:
* **slow即為要刪除的node**

## Python:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def deleteMiddle(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy=ListNode(0)
        dummy.next=head
        pre=dummy
        slow=head
        fast=head
        while fast and fast.next:
            pre=slow
            slow=slow.next
            fast=fast.next.next
        #slow為要刪除的node
        pre.next=slow.next
        return dummy.next

## C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        ListNode* slow=head, *fast=head, *pre=dummy;
        while (fast && fast->next){
            pre=slow;
            slow=slow->next;
            fast=fast->next->next;
        }
        pre->next=slow->next;
        return dummy->next;
    }
};