Problem: 2095. 删除链表的中间节点
思路
利用快慢指针,快指针每次走两步,慢指针每次走一步(循环退出条件是fast指针不为空同时fast.next不为空),但是我们容易发现这样到最后slow指针正好指向我们需要删除的节点,由于没有前指针,这样我们不便操作。此时可以借助虚拟头节点解决此问题。
解题方法
1.慢指针指向虚拟头节点,快指针指向链表头节点
2.快指针每次走两步,慢指针走一步(循环退出条件是fast指针不为空同时fast.next不为空);
3.最后将慢指针指向的节点的next指针指向其下一个节点的下一个节点(solw.next = solw.next.next)
复杂度
- 时间复杂度:
O ( n ) O(n) O(n)文章来源:https://www.toymoban.com/news/detail-742105.html
- 空间复杂度:
O ( 1 ) O(1) O(1)文章来源地址https://www.toymoban.com/news/detail-742105.html
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;
}
}
到了这里,关于力扣2095.删除链表的中间节点(java快慢指针)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!