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

蔚落 2022-09-08 15:52 143阅读 0赞

## 前言 ##

题目：[19. 删除链表的倒数第N个结点][19. _N]

参考答案：[删除链表的倒数第N个节点-力扣官方题解][N_-]

## 提交代码 ##

单链表，寻找倒数第n个元素。由于没有前指针，只能顺数遍历。先遍历一遍得到长度len。倒数第n个元素的下标=len-n。思路简单有效。

题目的进阶提示，“你能尝试使用一趟扫描实现吗？”。我想了想，寻找倒数第n个元素，自然会想到栈。遍历一遍将链表指针全部压栈。再弹栈n次，第n个弹出的元素即为待删除的元素，它前一个元素在栈顶。但是这种方式，和上面的思路，计算复杂度相同。

想不出来，我去瞄了下答案。答案使用了双指针来实现一次扫描。一个指针在前，一个指针在后。两个指针间距为n。当后一个指针遍历结束，前一个指针刚好指向倒数第n个节位置(双指针的边界效果，good)。

PS:这道题目的难度或许应该标为简单，没有到中等的难度。

### 计算链表长度 ###

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 *result=nullptr;
    
            // 遍历得到总长度
            int len = 0;
            ListNode *it = head;
            while(it != nullptr){
                len++;
                it=it->next;
            }
    
            // 第n个节点的顺序下标=总长度-倒数第n个节点
            int index = len-n;
            if(index >=0){
                ListNode *dummyHead = new ListNode(0,head);// 添加一个伪头部，便于删除
                ListNode *prevIt = dummyHead;
                it = head;
                for(int i = 0; i<index; i++){ // 遍历到待删除节点位置
                    prevIt = it;
                    it = it->next;
                }
                prevIt->next = it->next;
                delete it;
    
                result =  dummyHead->next;
                delete dummyHead;
            }else{ // 不再删除范围内
                result =  head;
            }
    
            return result;
        }
    };

### 双指针 ###

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 *dummyHead = new ListNode(0,head); // 添加一个哑节点
            ListNode *slowIt=dummyHead, *fastIt=head;
            ListNode *result;
    
            // 让快指针超前慢指针n+1步。(初始化的时候已超前一步，多合法的超前一步，不用保存倒数第n个元素的前指针)
            for(int i=0; i<n; i++)
                if(fastIt!=nullptr)
                    fastIt = fastIt->next;
                else
                    return head; //这个n超过链表长度，非法
            
            // 一起向前走，当快指针为空时，慢指针举例快指针n+1个距离，即倒数第n个元素的前一个元素
            while(fastIt!=nullptr){
                fastIt = fastIt->next;
                slowIt = slowIt->next;
            }
    
            // 删除倒数第n个元素
            ListNode *it = slowIt->next; // 待删除元素
            slowIt->next = it->next;
            delete it;
    
            // 删除伪头结点
            result = dummyHead->next;
            delete dummyHead;
    
            return result;
        }
    };

[19. _N]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[N_-]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/