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

浅浅的花香味﹌ 2023-02-14 02:52 23阅读 0赞

### Leetcode 19. 删除链表的倒数第N个节点 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

题目链接：[https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/][https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]

> 基本思路是：  
> 使用双指针，先让一个指针从头结点开始，向右移动 n + 1 步，  
> 然后第二个指针再向右移动，直到第一个指针移动到链表尾部，  
> 此时第二个指针正好指向 要删除节点的前置节点。  
> 这里注意的是 我们使用 n + 1 代替原来的 n ,因为要删除节点 n,  
> 我们必须知道节点 n-1。而使用 n + 1会出现越界问题，这里需要处理一下，  
> 即：链表走到尾部，但是 n 还是没有减完，即 n!=0,说明此时删除的就是头结点  
> 直接将头结点指向下一个节点即可

代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。

# 2、问题解决 #

笔者以`C++`方式解决。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "queue"
    #include "set"
    #include "map"
    #include "cstring"
    #include "stack"
    
    /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    
    struct ListNode { 
        int val;
        ListNode *next;
    
        ListNode(int x) : val(x), next(NULL) { }
    };
    
    class Solution { 
    public:
        ListNode *removeNthFromEnd(ListNode *head, int n) { 
            // 删除链表的倒数第N个节点
            dealChen(head, n);
            return head;
        }
    
        /** * 删除链表的倒数第N个节点 * 基本思路是： * 使用双指针，先让一个指针从头结点开始，向右移动 n + 1 步， * 然后第二个指针再向右移动，直到第一个指针移动到链表尾部， * 此时第二个指针正好指向 要删除节点的前置节点。 * 这里注意的是 我们使用 n + 1 代替原来的 n ,因为要删除节点 n, * 我们必须知道节点 n-1。而使用 n + 1会出现越界问题，这里需要处理一下， * 即：链表走到尾部，但是 n 还是没有减完，即 n!=0,说明此时删除的就是头结点 * 直接将头结点指向下一个节点即可 * @param head 这里注意是引用，因为可能要修改 head 的值（即删除的是头结点） * @param n */
        void dealChen(ListNode *&head, int n) { 
            // 定义双指针
            ListNode *head1 = head;
            ListNode *head2 = head;
            // 使用 n + 1 代替原来的 n
            // 使得 第一个指针移动到链表尾部时第二个指针正好指向 要删除节点的前置节点
            n = n + 1;
    
            // 将第一个节点往右移动 n 个距离，注意这里的 n 是我们修改后的 n+1
            while (head1 != NULL && n > 0) { 
                head1 = head1->next;
                n--;
            }
    
            // n!=0,说明此时删除的就是头结点
            if (n > 0) { 
                head = head->next;
                return;
            }
    
            // 双指针一起移动，直到第一个指针到达链表尾部
            while (head1 != NULL) { 
                head1 = head1->next;
                head2 = head2->next;
            }
            // 删除指定节点
            head2->next = head2->next->next;
        }
    };
    
    int main() { 
        ListNode *pNode1 = new ListNode(1);
        ListNode *pNode2 = new ListNode(2);
        ListNode *pNode3 = new ListNode(3);
        ListNode *pNode4 = new ListNode(4);
        ListNode *pNode5 = new ListNode(5);
    
        pNode1->next = pNode2;
        pNode2->next = pNode3;
        pNode3->next = pNode4;
        pNode4->next = pNode5;
        pNode5->next = NULL;
    
    // pNode1->next = NULL;
    
        Solution *pSolution = new Solution;
        ListNode *pNode = pSolution->removeNthFromEnd(pNode1, 2);
        while (pNode != NULL) { 
            cout << pNode->val << " ";
            pNode = pNode->next;
        }
        cout << endl;
        system("pause");
        return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]

有点菜，有时间再优化一下。

# 3、总结 #

难得有时间刷一波`LeetCode`, 这次做一个系统的记录，等以后复习的时候可以有章可循，同时也期待各位读者给出的建议。算法真的是一个照妖镜，原来感觉自己也还行吧，但是算法分分钟教你做人。前人栽树，后人乘凉。在学习算法的过程中，看了前辈的成果，受益匪浅。  
感谢各位前辈的辛勤付出，让我们少走了很多的弯路！  
哪怕只有一个人从我的博客受益，我也知足了。  
点个赞再走呗！欢迎留言哦！

[https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200531201024240.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3,size_16,color_FFFFFF,t_70