【面试经典 150 | 链表】删除链表的倒数第 N 个结点

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：统计节点个数
- 方法二：双指针
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【链表-删除节点】【迭代】

题目来源

19. 删除链表的倒数第 N 个结点

解题思路

方法一：统计节点个数

思路

一种朴素的方法是首先统计链表中节点的个数 m，倒数第 n 个节点就是正数第 m - n + 1 个节点。我们从头结点开始，找到正数第 m - n 个节点（要删除节点的前一个节点），直接将该节点的指针指向下下个节点即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    const int getLength(ListNode* head) {
        int len = 0;
        while (head) {
            ++len;
            head = head->next;
        }
        return len;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        int m = getLength(head);
        ListNode* cur = dummy;
        for (int i= 0; i < m - n; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        return dummy->next;
    }
};

复杂度分析

时间复杂度： $O (m)$ ， $m$ 为链表的长度。

空间复杂度： $O (1)$ 。

方法二：双指针

思路

我们先用一个指针指向链表的第 n 个节点，此时增加另一个指针指向头结点，接着让两个指针同时向链表尾部移动，每一移动一个位置，当第一个指针到达 nullptr 时，我们也就找到了需要删除的节点。

如果我们利用代码中的 while 循环就找到了要删除节点的上一个节点，此时直接将该节点的指针指向下下个节点即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *first = head;
        ListNode *dummy = new ListNode(0, head);
        ListNode *second = dummy;

        for(int i = 0; i < n; ++i)
            first = first->next;
        
        while(first){
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        return dummy->next;
    }
};

复杂度分析

时间复杂度： $O (m)$ ， $m$ 为链表的长度。

空间复杂度： $O (1)$ 。