dede搭建网站教程,平顶山专业做网站公司,网站建设工单系统,ipfs做网站文章目录题目描述思路 代码题目描述
重点在于一趟扫描实现简单的做法#xff1a;一趟扫描长度#xff0c;一趟根据长度找到结点删除
思路 代码
两种特例情况#xff0c;见注释思路#xff1a;根据N构造两个快慢指针#xff0c;两指针直接差了N个结点。由此…
文章目录题目描述思路 代码题目描述
重点在于一趟扫描实现简单的做法一趟扫描长度一趟根据长度找到结点删除
思路 代码
两种特例情况见注释思路根据N构造两个快慢指针两指针直接差了N个结点。由此可以在扫描一趟结束的时候让慢指针刚好在可以解决问题的结点位置。
/*** 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) {// 特例1单个的情况直接返回null链表if(head.next null){return null;}// 快慢指针做法ListNode fast head, slow head;// 快针先行while(n--!0){fast fast.next;}// 特例2去掉头指针此处fastnull说明要去掉的就是头指针if(fast null){return head.next;}// 慢针开冲while(fast.next!null){fast fast.next;slow slow.next;}slow.next slow.next.next;return head;}
}时间复杂度O(n)一次遍历就完事空间复杂度O(1)
