力扣2095.删除链表的中间节点（java快慢指针）

本文主要是介绍力扣2095.删除链表的中间节点（java快慢指针），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

文章目录

思路
解题方法
复杂度
Code

思路

利用快慢指针，快指针每次走两步，慢指针每次走一步（循环退出条件是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;}
}