网站建设回龙观合肥网站建设佳蓝网络

Problem: 2095. 删除链表的中间节点

思路

利用快慢指针，快指针每次走两步，慢指针每次走一步（循环退出条件是fast指针不为空同时fast.next不为空），但是我们容易发现这样到最后slow指针正好指向我们需要删除的节点，由于没有前指针，这样我们不便操作。此时可以借助虚拟头节点解决此问题。

解题方法

1.慢指针指向虚拟头节点，快指针指向链表头节点
2.快指针每次走两步，慢指针走一步（循环退出条件是fast指针不为空同时fast.next不为空）；
3.最后将慢指针指向的节点的next指针指向其下一个节点的下一个节点（solw.next = sole.next.next）

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(1)$

Code

/*** 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) {ListNode dummy = new ListNode();dummy.next = head;ListNode fast = head;ListNode slow = dummy;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
}