puppy-dog-cute-love-cat-mammal

前面,我们实现了 两个有序链表的合并 操作,本篇来聊聊,如何删除一个链表的倒数第 N 个节点。

删除单链表倒数第 N 个节点

Leetcode 19. Remove Nth Node From End of List

给定一个单链表,如: 1->2->3->4->5,要求删除倒数第 N 个节点,假设 N = 2,并返回头节点。

则返回结果:1->2->3->5 .

解法一

这一题的难度标记为 medium,解法一比较容易想出来,我个人觉得难度不大。

思路

循环两遍:

  1. 先遍历一遍,求得整个链表的长度。
  2. 再遍历一遍,当总长度 len 减去 n ,恰好等于循环的下标 i 时,就找到对应要删除的目标元素,将 prev 节点与 next 节点连接起来即可。

代码

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {

public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return null;
}
int len = 0;
for(ListNode curr = head ; curr != null;){
len++;
curr = curr.next;
}

if(len == 0){
return null;
}

// remove head
if(len == n){
return head.next;
}

ListNode prev = null;
int i = 0;
for(ListNode curr = head; curr != null;){
i++;
prev = curr;
curr = curr.next;

if(i == (len - n)){
prev.next = curr.next;
}
}
return head;
}
}

Leetcode 测试的运行时间为 6ms,超过了 98.75% 的 java 代码。

解法二

这种解法,比较巧妙,没有想出来,查了网上的解法,思路如下:

思路

只需要循环一遍,定义两个指针,一个快指针,一个慢指针,让快指针的巧好领先于慢指针 n 步。当快指针到达 tail 节点时,满指针巧好就是我们需要删除的目标元素。

代码

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {

public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
for(int i = 0; i < n; i++){
fast = fast.next;
}

if(fast == null){
return slow.next;
}

ListNode prev = null;
for(ListNode curr = slow; curr != null; ){
// when fast arrived at tail, remove slow.
if(fast == null){
prev.next = curr.next;
break;
}
prev = curr;
curr = curr.next;
// move fast forward
fast = fast.next;
}
return head;
}
}

这段代码在 LeetCode 上的测试结果与解法一的一样。

这种解法与之前的 链表环检测 题目中都使用到了快慢指针,用来定位特定的元素。

相关练习

参考资料