题目描述
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 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 <= 300 <= Node.val <= 1001 <= n <= sz
解题思路
计算链表长度
栈
双指针
代码实现
计算链表长度
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
| public class Solution19Case1 {
public static ListNode removeNthFromEnd(ListNode head, int n) {
int length = 0;
ListNode temp =head;
while (temp != null) {
length++;
temp = temp.next;
}
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
for (int i = 1; i < length - n + 1; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}
public static void main(String[] args) {
ListNode node5 = new ListNode(5);
ListNode node4 = new ListNode(4, node5);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
ListNode node1 = new ListNode(1, node2);
ListNode listNode = removeNthFromEnd(node1, 2);
System.err.println(listNode);
}
}
|
栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution19Case3 {
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
Deque<ListNode> stack = new LinkedList<>();
ListNode curr = dummy;
while (curr != null) {
stack.push(curr);
curr = curr.next;
}
for (int i = 0; i < n; i++) {
stack.pop();
}
ListNode peek = stack.peek();
peek.next = peek.next.next;
return dummy.next;
}
}
|
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Solution19Case2 {
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
for (int i = 0; i < n; i++) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
|