题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
1
2
| 输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
|
示例 2：
1
2
| 输入：head = [1], n = 1
输出：[]
|
示例 3：
1
2
| 输入：head = [1,2], n = 1
输出：[1]
|
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
我的解答
链表题，还是通用思路双指针。快慢指针，快指针先走n步，后慢指针在开始走，快指针走到结尾，慢指针正好指向倒数第n个节点。
又因为需要删除的是第n个节点，所以慢指针在慢一步，即可指向倒数n+1个节点，然后改变next指向即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
ListNode p1 = head, dummy = new ListNode(0, head), p2 = dummy;
for (int i = 0; i < n; i++) {
p1 = p1.next;
}
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
p2.next = p2.next.next;
return dummy.next;
}
|
官方参考
递归回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int count =0;
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return null;
}
head.next = removeNthFromEnd(head.next, n);
count++;
if(count == n){
return head.next;
}
return head;
}
|