【算法题解】13. 删除链表的倒数第 N 个结点

这是一道 中等难度 题。

题目来自：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

题目

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

示例1:

输入：head = [1,2,3,4,5], n = 2 
输出：[1,2,3,5]

示例2:

输入：head = [1], n = 1 
输出：[]

示例3:

输入：head = [1,2], n = 1 
输出：[1]

提示：

链表中结点的数目为 sz

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

解法一：计算链表长度

想要删除链表中的一个节点，最简单的做法就是找到这个节点的前一个节点，然后将前一个节点的next指针指向需删除节点的下一个节点。如删除节点4，即将节点3 的下一个节点直接指向节点5。

题目要求删除的是倒数第n个节点，由于单链表只能从头开始往后找，所以我们需要知道需删除节点的位置从前开始数是应该是第几个。

可以先从头到尾循环一遍计算出总节点数total，那么被删除节点的位置deleteIndex应该是total + 1 – n，被删节点的前一个位置是total – n。

然后从头开始循环第二遍，直接找到total – n这个位置的节点并记为pre，然后删除pre的下一个节点。

Java 代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode protect = new ListNode(0);
        protect.next = head;

        int total = 0;
        while(head != null){
            total++;
            head = head.next;
        }

        int deleteIndex = total + 1 - n;
        
        ListNode pre = protect;
        for(int i = 1; i < deleteIndex; i++){
            pre = pre.next;
        }
        pre.next = pre.next.next;
       
        return protect.next;
    }
}

Go 代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 * Val int
 * Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {

    // 保护节点
    protect := &ListNode{0, head}

    // 计算链表长度
    total := 0
    for head != nil {
        total++
        head = head.Next
    }

    // 被删除节点位置
    deleteIndex := total + 1 - n

    // 找到删除节点的前一个
    pre := protect
    for i := 1; i < deleteIndex; i++ {
        pre = pre.Next
    }

    pre.Next = pre.Next.Next

    return protect.Next

}

复杂度分析

时间复杂度：需要循环两遍节点，第一遍是total次，第二遍是total – n次，总的来说是线性的时间复杂度， N 位链表总节点数。

空间复杂度：常数级空间复杂度。

解法二：双指针

解法一总共扫描了2次，题目进阶要求扫描1次如何解题？

要删除倒数第n个节点，我们需要找到倒数第n + 1个节点。在扫描一次的前提下，我们可以使用双指针来解题：

1. 先定义2个指针first和second并让它们都指向保护节点。

2. second指针单独向后移动n + 1 个节点。

3. 当first和second之间相差n + 1个节点时，first指针跟随second指针一起向后移动。

4. 当second指针指向null的时候，这个时候first指针刚好指向删除节点的前一个节点。

5. 删除指定节点。

Java 代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode protect = new ListNode(0);
        protect.next = head;

        ListNode first = protect, second = protect;
        for(int i = 1; i <= n + 1; i++){
            second = second.next;
        }

        while(second != null){
            second = second.next;
            first = first.next;
        }
        first.next = first.next.next;

        return protect.next;
    }
}

Go 代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 * Val int
 * Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {

    protect := &ListNode{0, head}

    first, second := protect, protect
    for i := 1; i <= n + 1; i++ {
        second = second.Next
    }

    for second != nil {
        second = second.Next
        first = first.Next
    }

    first.Next = first.Next.Next

    return protect.Next
}