T19题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题过程

解法一

思路

常规方法… 先计算，是正数第size-n个 设置一个变量，标记节点走一步就+1，直到定位到目标节点为止

解法二

思路

使用快慢双指针firstNode以及lastNode 开始时，firstNode指针指向head，而lastNode指针需要先指向一个哑节点，定位到目标节点的前驱节点，便于删除节点 哑节点：ListNode dummyNode = new ListNode(0,head)；这样哑节点的下一个节点就是头节点了

实现代码

public ListNode removeNthFromEnd(ListNode head, int n) {
          
   
        //使用快慢指针
        //设first指针先走n步，当它刚走n步的时候，last指针就开始跟着first指针一起走

        ListNode firstNode = head;
        ListNode dummyNode = new ListNode(0,head);
    	ListNode lastNode = dummyNode;
        int count = 0;
    //这里会有点绕，关于什么时候lastNode开始移动，官方解答在一个循环里让firstNode先走，很容易懂
        while(firstNode.next != null){
          
   
            firstNode = firstNode.next;
            count++;
            if(count>=n){
          
   
                lastNode = lastNode.next;
            }
        }
    //我这里还考虑了是否删除的是原头节点，与官方解答比起来，就很多余
    //没有考虑到dummyNode节点的下一个节点就是新的头节点
        if (lastNode.next == head){
          
   
            return head.next;
        }

        lastNode.next = lastNode.next.next;
        return head;
    }

官方解答（更加清晰易懂，向他们学习！）

public ListNode removeNthFromEnd(ListNode head, int n) {
          
   
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
          
   
            first = first.next;
        }
        while (first != null) {
          
   
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
     //直接返回哑节点的下一个节点了，不管删除的是不是原先的头节点
        ListNode ans = dummy.next;
        return ans;
    }

解题收获

疑惑点

如果删除的是头节点怎么办，使用双指针的时候我要怎么定位它，以及怎么删除它，没有想到可以设置一个哑节点 使用while循环让firstNode先走，在判断lastNode什么时候走的时候脑袋有点混乱