459. 删除链表的倒数第N个节点的3种方式

Original 山大王wld 数据结构和算法 2022-05-09

收录于合集 #算法图文分析 161个

Why can't we savor the precious moments？

我们为什么不慢慢享受美好时光？

问题描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为
1->2->3->5.

说明：

给定的 n 保证是有效的。

非递归解决

这题让删除链表的倒数第n个节点，首先最容易想到的就是先求出链表的长度length，然后就可以找到要删除链表的前一个结点，让他的前一个结点指向要删除结点的下一个结点即可，这里就以示例为例画个图看一下

再来看下代码

 1public ListNode removeNthFromEnd(ListNode head, int n) {
 2    ListNode pre = head;
 3    int last = length(head) - n;
 4    //如果last等于0表示删除的是头结点
 5    if (last == 0)
 6        return head.next;
 7    //这里首先要找到要删除链表的前一个结点
 8    for (int i = 0; i < last - 1; i++) {
 9        pre = pre.next;
10    }
11    //然后让前一个结点的next指向要删除节点的next
12    pre.next = pre.next.next;
13    return head;
14}
15
16//求链表的长度
17private int length(ListNode head) {
18    int len = 0;
19    while (head != null) {
20        len++;
21        head = head.next;
22    }
23    return len;
24}

双指针求解

上面是先计算链表的长度，其实不计算链表的长度也是可以，我们可以使用两个指针，一个指针fast先走n步，然后另一个指针slow从头结点开始，找到要删除结点的前一个结点，这样就可以完成结点的删除了。

 1public ListNode removeNthFromEnd(ListNode head, int n) {
 2    ListNode fast = head;
 3    ListNode slow = head;
 4    //fast移n步，
 5    for (int i = 0; i < n; i++) {
 6        fast = fast.next;
 7    }
 8    //如果fast为空，表示删除的是头结点
 9    if (fast == null)
10        return head.next;
11
12    while (fast.next != null) {
13        fast = fast.next;
14        slow = slow.next;
15    }
16    //这里最终slow不是倒数第n个节点，他是倒数第n+1个节点，
17    //他的下一个结点是倒数第n个节点,所以删除的是他的下一个结点
18    slow.next = slow.next.next;
19    return head;
20}

递归解决

我们知道获取链表的长度除了上面介绍的一种方式以外，还可以写成递归的方式，比如

1//求链表的长度
2private int length(ListNode head) {
3    if (head == null)
4        return 0;
5    return length(head.next) + 1;
6}

上面计算链表长度的递归其实可以把它看做是从后往前计算，当计算的长度是n的时候就表示遍历到了倒数第n个节点了，这里只要求出倒数第n+1个节点，问题就迎刃而解了，来看下代码

 1public ListNode removeNthFromEnd(ListNode head, int n) {
 2    int pos = length(head, n);
 3    // 说明删除的是头节点
 4    if (pos == n)
 5        return head.next;
 6    return head;
 7}
 8
 9// 获取节点所在位置，逆序
10public int length(ListNode node, int n) {
11    if (node == null)
12        return 0;
13    int pos = length(node.next, n) + 1;
14    //获取要删除链表的前一个结点，就可以完成链表的删除
15    if (pos == n + 1)
16        node.next = node.next.next;
17    return pos;
18}