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

LeetCode100之删除链表的倒数第N个节点(19)--Java

news 2024/11/14 20:37:02

1.问题描述

给你一个链表，删除链表的倒数第 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]

提示

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

难度等级

中等

题目链接

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

2.解题思路

这道题要我们删除链表的倒数第N个结点，它的难点就在于如何找打倒数第N个结点。

不过这个难点也很容易就可以解决，我们只需要定义前后的两个指针，然后让前指针先走N个节点，这样前后两个指针就相差了N个节点。在这种情况下，如果前后指针同时遍历，当前指针到达链表末尾时，前指针所在节点为倒数第一个节点，后指针所在节点为倒数第(N+1)个节点，要删除的节点就在后指针的下一个节点。

        //定义前后两个指针ListNode front = head;ListNode back = head;

上面的想法可以解决大部分情况，但是当要删除的节点是头结点时，上面的这种情况就行不通了。假设链表就a个节点，要求我们删除倒数第a个节点，那前指针走不到(a+1)个节点处，没有那么多节点可以走。所以我们可以用一个变量来统计前指针比后指针先走的节点个数，如果小于N，说明要删除的就是头结点，我们直接把头节点删除就好了。

        //让前后两个指针相差n个节点int count = 0;while(count < n && front != null && front.next != null){front = front.next;count++;}//如果count还未等于n就退出//说明要删除的节点是头结点if(count < n){return head.next;}

如果要删除的不是头结点，那么在前指针先走完N个节点后，前后指针就可以开始行动了，直到前指针到达链表末尾。

        //同时移动前后两个指针，直到前指针到达链表末尾while(front.next != null){front = front.next;back = back.next;}

前指针到达链表末尾后，后指针也就到达了倒数第(N+1)个节点，直接将后指针的下一个节点指针指向倒数第(N-1)个节点，删除倒数第N个节点即可。

        //走到这一步，后指针的下一个节点就是倒数第n个节点//将它删掉back.next = back.next.next;

最后将链表的头结点返回。

3.代码展示

/*** 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) {//定义前后两个指针ListNode front = head;ListNode back = head;//让前后两个指针相差n个节点int count = 0;while(count < n && front != null && front.next != null){front = front.next;count++;}//如果count还未等于n就退出//说明要删除的节点是头结点if(count < n){return head.next;}//同时移动前后两个指针，直到前指针到达链表末尾while(front.next != null){front = front.next;back = back.next;}//走到这一步，后指针的下一个节点就是倒数第n个节点//将它删掉back.next = back.next.next;//返回头结点return head;}
}