题解 | #删除链表的倒数第n个节点#
删除链表的倒数第n个节点
https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6
关于这道题可以分成两步，第一步就是找到节点，直接拿我们上一题的代码来用
public ListNode find(ListNode head,int k){
ListNode fast = head;
ListNode slow = head;
while(k-- > 0){
if(fast == null) return null;
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
然后就是删除，删除的话这里我们可以构造一个虚拟节点，就可以包含很多特殊的测试用例，比如说让你删除头结点之类的
public class 删除链表中倒数第K个节点 {
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
ListNode node = new ListNode(0);
node.next = head;
ListNode fast = find(head,n);
ListNode slow = node;
while(slow.next != fast){
slow = slow.next;
}
slow.next = slow.next.next;
return node.next;
}
public ListNode find(ListNode head,int k){
ListNode fast = head;
ListNode slow = head;
while(k-- > 0){
if(fast == null) return null;
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
当然这道题大可以不必这么做，因为它有一个很特殊的限制条件
备注： 题目保证 n 一定是有效的所以可以直接就去寻找到要删除的节点，然后为了方便起见这次我们让fast指针从虚拟节点走起，这样会导致什么情况呢？就是slow节点的下一个节点就是要删除的节点
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
ListNode node = new ListNode(0);
node.next =head;
ListNode fast = node;
while(n-- > 0){
fast = fast.next;
}
ListNode slow = node;
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return node.next;
}
领导找我续签到明年3、4月我要继续吗