06 —删除链表的倒数第 N 个结点【LeetCode 19】

题目

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

示例一：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例二：

输入：head = [1], n = 1
输出：[]

示例三：

输入：head = [1,2], n = 1
输出：[1]

提示：

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100

• 1 <= n <= sz

  进阶：你能尝试使用一趟扫描实现吗？

解题

解法一

思路

为了实现一趟扫描，我的思路想法是首先，遍历链表，将链表的每个地址都存入ArrayList中，然后遍历完毕后，得出链表长度，得出需要删除结点的地址，然后直接去ArrayList中对应的索引处的地址删除即可。

解决

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //遍历链表，将链表的每个地址都存入ArrayList中，然后遍历完毕后，得出链表长度，得出需要产出结点的地址，然后直接去ArrayList中对应的索引处的地址删除即可。
        //声明ArrayList用来存地址
        ArrayList<ListNode> arr = new ArrayList<>();
        //记录节点数，结点数默认为1
        int num = 0;
        //声明移动结点node，初始为head
        ListNode node = head;
        //开始遍历链表
        while(node!=null){
            arr.add(node);
            node = node.next;
            num++;
        }
        //判断要删除的结点是不是最后一个

        if(num==n){     //判断要是删除的是头节点
            head = head.next;
        }else if(n==1){ //表示需要删除的是最后一个结点
            arr.get(num-2).next = null;
        }else{
            //表示删除的是中间结点找到需要删除结点的前一个，((num+1)-n)-1索引为需要删除的结点
            arr.get(((num+1)-n)-2).next = arr.get(((num+1)-n));
        }
        return head;
    }
}

结果

> 2023/07/15 15:59:55    
解答成功:
    执行耗时:0 ms,击败了100.00% 的Java用户
    内存消耗:39.7 MB,击败了23.83% 的Java用户

解法二（来自LeetCode官方）

思路

使用双指针的方法，我们需要找到倒数第n个结点，可以使用两个指针first和second同时对链表进行遍历，并且first比second超前n个结点，当first遍历到链表的末位时，second恰好处于倒数第n个结点。

具体的，初始时，first和second均指向头结点，使用first对链表进行遍历，当遍历次数为n时，此时first和second间隔了n-1结点，即first比second超前了n个结点。然后两个指针同时继续前进，当first到达链表末尾的时候second恰好指向倒数第n个结点

解决

class Solution {
    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;
    }
}

//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/

结果

• 时间复杂度：O(L)，L是链表的长度；
• 空间复杂度：O(1)。