题目
给你一个链表，删除链表的倒数第 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
进阶：你能尝试使用一趟扫描实现吗？
分析
方法一：递归
方法二：双指针
1、定义哑节点
2、使用双指针找到倒数第n+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) {
// 方法一：递归
// return removeNthFromEnd01(head,n);
// 方法二：使用快慢指针
return removeNthFromEnd02(head,n);
}
// 方法一：使用递归
private static ListNode removeNthFromEnd01(ListNode head,int n){
// base case
if(head.next==null){
return null;
}
int num=0;
// 每轮递归都是再往head后面赋值
head.next=removeNthFromEnd01(head.next,n);
num++;
if(num==n){
return head.next;
}
return head;
}
// 方法二：使用双指针的方法（要删除倒数第n个节点，先找到倒数第n+1个节点）
private static ListNode removeNthFromEnd02(ListNode head,int n){
// 边界值的控制,定义一个亚节点
ListNode dummy=new ListNode(-1);
dummy.next=head;
// 定义方法，查找倒数第n+1个节点
ListNode node=findNode(dummy,n);
// 删除目标节点
node.next=node.next.next;
return dummy.next;
}
// 查找倒数第n+1个节点
private static ListNode findNode(ListNode head,int n){
// 定义双指针
ListNode p1=head;
ListNode p2=head;
// p1先走n+1B步
for(int i=0;i<=n;i++){
p1=p1.next;
}
// 然后再一起走，p2就自然找到了倒数第n+1个节点
while(p1!=null){
p1=p1.next;
p2=p2.next;
}
// 返回p2,目标节点位置的前一个节点
return p2;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96229.html
