1. question: 删除链表的倒数第N个结点（中等）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
示例 1：
输入：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]
|
提示：
1
2
3
4
| 链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
|
2. answers
这道题最直观的做法还是比较明确的，和上一道题的思路一样。先将原链表反转，然后删除第n个节点，最后将删除后的链表反转即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| public class Solution_0037 {
public static ListNode reverseList(ListNode head) {
ListNode newHead = new ListNode();
ListNode temp;
while(head != null) {
temp = head.next;
head.next = newHead.next;
newHead.next = head;
head = temp;
}
return newHead.next;
}
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode tempResult = reverseList(head);
ListNode result;
if(n == 1) {
return reverseList(tempResult.next);
}
result = tempResult;
for (int i = 1; i < n - 1; i++) {
tempResult = tempResult.next;
}
tempResult.next = tempResult.next.next;
return reverseList(result);
}
public static void main(String[] args) {
ListNode ln1 = new ListNode(5);
ListNode ln2 = new ListNode(4, ln1);
ListNode ln3 = new ListNode(3, ln2);
ListNode ln4 = new ListNode(2, ln3);
ListNode ln5 = new ListNode(1, ln4);
ListNode listNode = removeNthFromEnd(ln2, 1);
while(listNode != null) {
System.out.println(listNode.val);
listNode = listNode.next;
}
}
}
|
参考了其他博客，可以采用双指针的做法。因为删除的是倒数第n个节点，也就是说和尾节点相差n-1个节点。可以采用快慢指针，使得两个指针在最开始的时候就相差n个节点，依次向后遍历，当快指针到达尾结点的时候，此时慢指针就是要删除节点的前一个节点，进行删除操作即可。代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| public class Solution_0037_02 {
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode newHead = new ListNode();
newHead.next = head;
ListNode fast = newHead;
ListNode slow;
while(n > 0) {
fast = fast.next;
n--;
}
slow = newHead;
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return newHead.next;
}
public static void main(String[] args) {
ListNode ln1 = new ListNode(5);
ListNode ln2 = new ListNode(4, ln1);
ListNode ln3 = new ListNode(3, ln2);
ListNode ln4 = new ListNode(2, ln3);
ListNode ln5 = new ListNode(1, ln4);
ListNode listNode = removeNthFromEnd(ln1, 1);
while(listNode != null) {
System.out.println(listNode.val);
listNode = listNode.next;
}
}
}
|
一些细节补充如下所示：
上一个方法，本质上也是O(n)的时间复杂度，但是扫描了3次。这里参考博客，改进一下
采用双指针法。要删除的是倒数第n个节点，也就是说，要删除的节点距离尾结点相差n个。那么采用双指针法：快指针和慢指针，使得二者在开始遍历的时候，就相差n个节点。依次向后遍历，那么当快指针到达尾结点的时候，此时的慢指针必定是要删除的那个节点。
如此只遍历了一次。
上面只是大致的思路，具体的细节需要纠正。比如我们要找的是要删除节点的前一个节点。
比如，如果要删除的是第一个节点，也就是倒数第length个节点，依照上面的流程，slow指针还来不及赋值就结束了，也就是说slow指针此时指向的就是第0个节点。也就是说，必须要构造一个链表，比原链表要长一点，此时加一个空的头节点即可。
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
