19.删除链表的倒数第N个节点
问题:如何能使用一趟扫描实现? 基本思想: 1.需要创建虚拟头结点,可能存在删除倒数第n个节点为头结点的情况。添加虚拟头结点便可以统一处理。 2.本题用快慢指针来实现,初始状态时,令slow指针指向dummy虚拟节点,fast指针需要指向第n+1个节点。 这样才能保证结束状态时,fast指针指向null时,slow在倒数第N个节点的前一个节点,这样便于删除操作! 完整代码:
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
for(int i=0; i<=n; i++){
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
|