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

Myth丶恋晨 2024-03-27 10:50 18阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解法一：计算链表长度
     *   *  Java 代码实现
         *  Go 代码实现
         *  复杂度分析
     *  解法二：双指针
     *   *  Java 代码实现
         *  Go 代码实现
         *  复杂度分析

> 这是一道 **中等难度** 的题。  
> 题目来自：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

### 题目 ###

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

**示例 1**：  
![删除链表的倒数第 N 个结点][N]

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

**示例 2：**

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

**示例 3：**

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

**提示：**  
链表中结点的数目为  s z sz sz

1.   1 < = s z < = 30 1 <= sz <= 30 1<=sz<=30
2.   0 < = N o d e . v a l < = 100 0 <= Node.val <= 100 0<=Node.val<=100
3.   1 < = n < = s z 1 <= n <= sz 1<=n<=sz

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

### 解法一：计算链表长度 ###

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

题目要求删除的是倒数第`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
    
    }

#### 复杂度分析 ####

**时间复杂度**： O ( N ) O(N) O(N), 需要循环两遍节点，第一遍是`total`次，第二遍是`total - n`次，总的来说是线性的时间复杂度， N 位链表总节点数。  
**空间复杂度**： O ( 1 ) O(1) O(1), 常数级空间复杂度。

### 解法二：双指针 ###

解法一总共扫描了`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.  删除指定节点。  
    ![删除链表的倒数第 N 个结点][N 2]

#### 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
    }

#### 复杂度分析 ####

**时间复杂度**： O ( N ) O(N) O(N), 两个循环加起来`second`指针刚好从头走到尾，时间复杂度为链表长度。  
**空间复杂度**： O ( 1 ) O(1) O(1), 常数级空间复杂度。

[N]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/6881649c847a4bbfa5534b2ab9f6d771.png
[N 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ff1b3d9e68f2427baf397651b6d2f63f.png
[N 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/21be350127924c8ca6d11ad7b5369e90.png