删除链表的倒数第n个元素

删除链表的倒数第n个元素

双指针的经典应用

fast指针先走 n+1 步（n+1 是使slow指针能指向删除节点的前一个节点），再使fast指针和slow指针同时往前走 直至 fast 指针为 null。(当fast指针为空时，即fast走到了链表末尾，此时两指针距离 n+1 ，即为倒数第n个元素的前一元素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟头节点
        ListNode cur = new ListNode(0);
        cur.next = head;
        ListNode slow = cur,fast=cur;

        // fast 先走 n+1 步
        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 cur.next;
    }
}