leetcode刷题-19删除链表的倒数第 N 个结点

编写语言：java； 分析自己的思路和其他人的思路的差别； labuladong的思路： 处理“删除倒数第n个节点”的问题，使用两个指针p1和p2，两个指针之间，间隔n+1个节点，然后同时移动，当p1指向null时，p2.next就是要删除的节点。 1.删除倒数第 n 个，要先找倒数第 n + 1 个节点 2.先使用for找到第n+1个节点，安排p1指向第n+1个节点 3.然后再同时移动p1和p2

public ListNode removeNthFromEnd(ListNode head, int n) {
          
   
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    ListNode x = findFromEnd(dummy, n + 1);
    // 删掉倒数第 n 个节点
    x.next = x.next.next;
    return dummy.next;
}
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
          
   
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
          
   
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
          
   
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

我的思路， 1.判断是不是链表中只有一个节点，且要删除此节点，如果是，直接删除，结束 2.利用while循环，直到p1==null 2.1移动p1,判断p2是否应该一起移动 3.删除p2.next这个节点

public ListNode removeNthFromEnd(ListNode head, int n) {
          
   
        ListNode dummy=new ListNode(-1);
        ListNode p2=dummy;
        dummy.next=head;
        ListNode p1=head;
        int i=0;
        if(dummy.next.next==null&&n==1)
        {
          
   
        //删除的节点是第一个
            dummy.next=null;
        }
        else{
          
   
             while(p1!=null)
        {
          
   
            p1=p1.next;
            if(i>=(n))
            {
          
   
                //到了出场的时候，但是别忘了i的初始值是0
                p2=p2.next;
            }
            i++;
        }
       //此时返回的指针p2的下一节点指着的就是想要删除的这个点
        p2.next=p2.next.next;
        }
        return dummy.next;
    }

区别： 我在写代码时，忽略了一些极端情况，后续单独把这些极端情况的处理方式通过if-else额外添加在代码中，导致代码很乱。 labuladong的代码中使用了一个虚拟节点头dummy，p1是从这个虚拟节点头开始的，很好地避免了极端的情况（删除的节点在第一个等情况） 使用虚拟节点保证了p1和p2之间的节点数至少为1的情况，如果不使用虚拟节点，那当链表长度为1，且要删除该节点时，p1和p2两个指针之间的节点数为0，就会出错。