LeetCode75-2095-Delete-Middle-Node

🧠 思路总结

• 链表没有index
  题目： 删除第 ⌊n / 2⌋ 个节点（0-based）

方法一：长度法

1. 遍历一次，算长度 n
2. 计算 middle = n / 2
3. 再走到 middle - 1
4. 删除 middle

方法二：快慢指针（最优解）

核心思想：slow 每次走 1 步, fast 每次走 2 步

• 这道题目不是要找中间的Node，而是要找 中间节点的前一个

• 删除指针的本质：prev.next = prev.next.next

✅ 代码（Java）

• 长度法：

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode() {}
   *     ListNode(int val) { this.val = val; }
   *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   * }
   */
  class Solution {
      public ListNode deleteMiddle(ListNode head) {
  
          if (head == null || head.next == null) {
              return null;
          }
  
          int count = 0;
          ListNode curr = head;
          while (curr != null) {
              count++;
              curr = curr.next;
          }
  
          int middle = count / 2;
          ListNode prev = head;
          for (int i = 0; i < middle - 1; i++) {
              prev = prev.next;
          }
          prev.next = prev.next.next;
          return head;
      }
  }

• 快慢指针

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode() {}
   *     ListNode(int val) { this.val = val; }
   *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   * }
   */
  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;
      }
  }