image.png
思路 双指针 时间复杂度O(n) 空间复杂度O1
首先还是先设置虚拟头节点, 方便处理删除头节点的情况
dummyHead.next = head设置
fast = dummyHead, slow = dummyHead;让
fast先走N步, slow再开始走. 当fast指向null时.说明走到了最后,此时slow的位置就是倒数第N个节点的位置要
删除倒数第N个节点, 我们必须拿到N前面那个节点 就是N -1,所以我们让fast走n+1步,当fast走到最后时, slow指向的位置就是倒数第N-1个节点.此时我们要操作
slow.next = slow.next.next即可删除倒数第N个节点看到一个网友评论的可优化的地方
第二层while循环有个优化点, 当fast.next != null 时候. fast不用走n + 1步
我个人觉得走n+1步好理解一点. 这个优化点刚开始我都没看明白为啥😄
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode slow = dummyHead;
ListNode fast = dummyHead;
n++;
while (n-- > 0 && fast != null) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
// 优化版
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode slow = dummyHead;
ListNode fast = dummyHead;
while (n-- > 0 && fast != null) {
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
