当前位置：首页 > article >正文

蓝桥与力扣刷题（19 删除链表的倒数第N个结点）

article 2025/2/9 12:41:25

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路＋代码：

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        /**
        思路：
        1.判断所给的链表是否为空链表，为空直接返回null
        2.删除某个节点使用架空思想来删除该节点，衔接到删除节点的下一个next
        3.创建一个新的链表存放删除节点后的链表
        4.双指针遍历链表，双指针从头节点开始依次遍历，fast快指针先遍历完链表，可迅速找到倒数第n个节点时，slow指针在遍历到第n个节点时，指向删除节点的下一个next节点
         */
        
        if(head == null){
            return null;
        }

        //创建一个新的链表存放删除节点后的链表
        ListNode newList = new ListNode(0);
        newList.next = head;

        //声明快慢指针
        ListNode fastNode = newList;
        ListNode slowNode = newList;

        //遍历链表，找到倒数第n个节点
        for(int i = 0;i < n;i++){
            fastNode = fastNode.next;
        }
 
        //遍历链表
        while(fastNode.next != null){
            //指针后移
            fastNode = fastNode.next;
            slowNode = slowNode.next;
            }
                        
        //架空删除节点的信息
        slowNode.next = slowNode.next.next;
        return newList.next;
    }
}

总结：这道题的难点就在于如何找到链表的倒数第N个结点并删除。因为单链表没有反向指针，所以无法使用左右指针来进行快速删除。只能使用双指针法，快指针迅速遍历完链表后，找到需要删除的倒数第N个结点，慢指针遍历到需要删除的倒数第N个结点时，使用架空思想（slow.next = slow.next.next）来达到删除倒数第N个结点的目的。

查看全文

http://www.kler.cn/a/537851.html