当前位置：网站首页>链表(五)——删除链表的倒数第N个节点

链表(五)——删除链表的倒数第N个节点

2022-07-20 15:48:00 【木棣%】

删除链表的倒数第N个节点

- 双指针

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

示例：

在这里插入图片描述

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

提示：

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

双指针

要删除倒数第n个节点，让p移动n步，然后让p和q同时移动，直到p指向链表末尾
删掉q所指向的节点

设置虚拟节点 dummyHead指向 head
设定双指针p 和q，初始都指向虚拟节点dummyHead
移动q，直到p与q之间相隔的元素个数为n
同时移动p与q，直到q指向的为NULL
将p的下一个节点指向下下个节点

class Solution {
    
    public ListNode removeNthFromEnd(ListNode head, int n) {
    
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode p = dummyHead;
        ListNode q = dummyHead;
        while (n-- > 0) {
    
            p = p.next;
        }
        // 待删除节点q的上一节点
        ListNode prev = null;
        while (p != null) {
    
            prev = q;
            q = q.next;
            p = p.next;
        }
        // 上一节点的next指针绕过 待删除节点q 直接指向q的下一节点
        prev.next = q.next;
        // 释放 待删除节点q 的next指针
        q.next = null;

        return dummyHead.next;
    }
}