前言

链表练习,继续
题目:力扣【19.删除链表的倒数第N个节点】


题目阅读

给你一个链表,删除链表的倒数第 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
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶:

你能尝试使用一趟扫描实现吗?

第一次尝试

先不考虑进阶,看如何实现。

思路:重点是什么找到倒数第n个节点。

  • 删除节点操作:用cur指向被删除节点的前一个节点。所以肯定得要一个虚拟头节点
  • 初始:cur = dummy_node;判断cur是不是在删除目标的前一个节点的位置?
  • 用search = cur,将search后移n位,看search->next是否为空:
    • n=1,将cur位置后移1位,search->next==nullptr;
    • n=2,将cur位置后移2位,search->next==nullptr;
    • n=3,将cur位置后移3位,search->next==nullptr;
    • 依次类推

代码实现(测试通过)

/**
 * 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* dummy_node = new ListNode(0,head);
            ListNode* cur = dummy_node;

            while(cur->next != nullptr){
                ListNode* search = cur;
                for(int i=0;i < n ;i++){
                    search = search->next;
                }
                if(search->next == nullptr){
                    //交换
                    ListNode* tmp = cur->next;
                    cur->next = cur->next->next;
                    delete tmp;
                    break;
                }
                cur = cur->next;
            }

            head = dummy_node->next;
            delete dummy_node;
            return head;
    }
};

检查:head=nullptr,符合逻辑。n=1,for循环条件判断正确。所以通过测试。
分析时间复杂度

while循环最差情况要遍历整个链表长度,for循环最差情况下执行n*(n+1)/2次,所以整体时间复杂度O(n^3)。

进阶

尝试使用一趟扫描。
思路:同样是线性结构,数组里面有快慢指针。这里能不能也用快慢指针?类似滑动窗口?

代码实现

/**
 * 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* dummy_node = new ListNode(0,head);
            ListNode* slow = dummy_node;
            ListNode* fast = dummy_node->next;
            int num = 1;//计数链表总长度

            if(slow->next != nullptr){
                while(fast->next != nullptr){
                    fast = fast->next;
                    num++;
                }
                if(num < n ){	//完善n超出链表长度,此时不删除,返回原链表,抛出异常
                	throw out_of_range("n > list_length");
                	return head;
                }
                
                for(int i = 0;i < num-n ;i++){
                    slow = slow->next;
                }
                ListNode* tmp = slow->next;
                slow->next = slow->next->next;
                delete tmp;
            }

            head = dummy_node->next;
            delete dummy_node;
            return head;
    }
};

思路正确:

  • 让fast先找到链表的最后一个元素,同时计数num,得到链表的总元素。
  • 收缩窗口,移动slow,移动num-n次,指向删除目标的前一个节点。slow到达位置之后,开始链表删除操作。

思路来源:个人博客【算法力扣刷题记录四【长度最小的子数组】】,学习到滑动窗口,同样是线性规则,所以借来使用。

进阶成功!!!


代码随想录学习

学习内容

同样是定义fast和slow,但过程也有区别。
我的操作:fast直接走到链表结尾,得出链表节点总数,再让slow后移num-n,到达删除目标的前一个位置。
参考操作

  • fast先走n步,这样窗口内包含n个节点,再让fast和slow同时移动,窗口内始终保持n个节点,当fast=nullptr时,slow恰好指向倒数第n个节点。
  • 由于删除操作,需要slow指向倒数第(n+1)个节点,所以修正让fast先走n+1步.

代码实现:

/**
 * 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* dummy_node = new ListNode(0,head);
            ListNode* slow = dummy_node;
            ListNode* fast = dummy_node;

            while(fast != nullptr  && n >= 0){ //n >= 0确保fast先走了n+1步
                fast = fast->next;
                n--;
            }
            if(n < 0){  //如果输入的n大于链表长度,n<0才算fast走到位,否则fast没走到位,但又已经到达链表尾部。返回原链表,不操作。不然就会把头节点删除,因为slow没有移动。
                while (fast != nullptr ){
                fast = fast->next;
                slow = slow->next;
                }
                ListNode* tmp = slow->next;
                slow->next = slow->next->next;
                delete tmp;
            }else{			//当n输入超过链表长度,抛出异常。
            	throw out_of_range("n out of list range");
			}
            
            

            head = dummy_node->next;
            delete dummy_node;
            return head;
    }
};

参考答案在第11行有操作空指针的风险,只是力扣用例没有检出来。
所以我在if(n < 0)可以保证输入的n小于链表长度,更完善。如果输入n超过链表长度,抛出out_of_range异常

可以回过头看[进阶]目录下代码完善。


总结

  • 删除链表节点:加虚拟头结点
  • “滑动窗口”思路:个人和参考,两种操作。
  • 代码随想录参考11行,个人认为有缺陷,没有保证n小于链表长度,作了补充。

(欢迎指正,转载标明出处)

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部