郑州做网站最好的公司,5条国内最新新闻,域名去哪里买,微信公众号菜单跳转网页怎么制作算法思想#xff1a;
使用了双指针法。下面是详细的算法思想#xff1a;
1. 引入虚拟头节点#xff08;dummy node#xff09;
为了处理链表的一些边界情况#xff08;比如删除头节点#xff09;#xff0c;我们在链表的头部引入了一个虚拟节点 dummy#xff0c;并让…算法思想
使用了双指针法。下面是详细的算法思想
1. 引入虚拟头节点dummy node
为了处理链表的一些边界情况比如删除头节点我们在链表的头部引入了一个虚拟节点 dummy并让它指向原来的头节点 head。这样无论我们要删除哪个节点处理过程都变得更加统一和简单。
2. 定义两个指针快指针fast和慢指针slow
我们使用两个指针fast 和 slow最初都指向虚拟头节点 dummy。快指针 fast 会比慢指针 slow 超前移动 n1 步。这样当 fast 指向链表末尾null时slow 刚好指向要删除节点的前一个节点。
3. 移动快指针
首先快指针 fast 先向前移动 n1 步这样可以确保快指针和慢指针之间相隔 n 个节点。
4. 同时移动快慢指针
接下来快慢指针一起向前移动直到快指针到达链表的末尾。这时慢指针 slow 就刚好处于要删除节点的前一个位置。
5. 删除节点
现在慢指针 slow 的下一个节点就是我们需要删除的节点。通过 slow.next slow.next.next我们跳过了这个节点达到了删除的目的。
6. 返回新的头节点
最后返回 dummy.next。注意链表的头节点可能发生了变化如果原来的头节点被删除因此我们返回虚拟节点 dummy 的下一个节点作为新的链表头节点。
代码核心思路总结
通过快慢指针法仅需遍历链表一次一次循环就可以找到倒数第N个节点并将其删除时间复杂度为 O(L)其中 L 是链表的长度。空间复杂度为 O(1)因为只用了常数级别的额外空间。
示例分析
假设输入链表为 [1, 2, 3, 4, 5]n 2即删除倒数第二个节点。
初始化fast 和 slow 都指向虚拟节点 dummy。快指针前移fast 先向前移动 n1 3 步指向节点 3。同步移动同时移动 fast 和 slow直到 fast 指向 null此时 slow 指向节点 3 的前一个节点即节点 2。删除节点通过 slow.next slow.next.next 删除节点 4最终链表变为 [1, 2, 3, 5]。
这样就成功地删除了倒数第2个节点。 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 removeNthFromEnd(ListNode head, int n) {ListNode dummyNode new ListNode(0);dummyNode.next head;ListNode slow dummyNode; //dummyNode,slow,fast都是引用类型ListNode fast dummyNode;for(int i 0; i n; i) { //快指针先移动 n1 步fast fast.next;}while(fast ! null) { //然后快慢指针一起移动slow slow.next;fast fast.next;}slow.next slow.next.next;return dummyNode.next;}
}
