力扣 19. 删除链表的倒数第N个结点
这一题主要考的是数学关系。
要想通过一趟扫描就找到倒数第n个结点,可以考虑用快的结点比慢的结点多走n步。
然后当快结点的next是null,就停止遍历。当然,为了方便处理链表,我们还是给原来的链表加上一个虚拟头结点dummyhead。
/**
* 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 dummyhead=new ListNode(-1);
dummyhead.next=head;
ListNode fast=dummyhead, slow=fast;
int i=0;
while(fast.next!=null){
if(i>=n){
slow=slow.next;
}
i++;
fast=fast.next;
}
slow.next=slow.next.next;
return dummyhead.next;
}
}