leetcode算法题-删除链表的倒数第N个节点

发表于 | 分类于 | 阅读次数: |

题目

本题为leetcode探索初级算法中链表章节的一题

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

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

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

说明：
给定的 n 保证是有效的。

进阶：
你能尝试使用一趟扫描实现吗？

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn2925/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的解法

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
/**
 * 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) {
        ListNode lengthHead = head;
        int length = 1;
        while(lengthHead.next != null){
            length++;
            lengthHead = lengthHead.next;
        }
        if(n == length){
            head = head.next;
            return head;
        }
        ListNode removePreHead = head;
        while(length != n + 1){
            length--;
            removePreHead = removePreHead.next;
        }
        removePreHead.next = removePreHead.next.next;
        return head;
    }
}

思路就是第一次循环得到长度，知道长度后删除倒数第n个就容易了。总共循环了两次，未能达到进阶要求。

官方解法

解法一：
图片名称

复杂度分析：
时间复杂度：O(L)O(L)，该算法对列表进行了两次遍历，首先计算了列表的长度 LL 其次找到第 (L - n)(L−n) 个结点。 操作执行了 2L-n2L−n 步，时间复杂度为 O(L)O(L)。
空间复杂度：O(1)O(1)，我们只用了常量级的额外空间。

跟我的思路大致相同，官方中使用了哑结点作为辅助，有效的避免极端情况，而我都是通过提前判断来实现的。

解法二：
图片名称

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

复杂度分析:
时间复杂度：O(L)O(L)，该算法对含有 LL 个结点的列表进行了一次遍历。因此时间复杂度为 O(L)O(L)。
空间复杂度：O(1)O(1)，我们只用了常量级的额外空间。

解法二使用两个指针先让第一个指针A移动n个距离，在两个指针一起移动，直到指针A移动到结尾。非常巧妙，学习了！