赞
踩
链表练习,继续
题目:力扣【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
进阶:
你能尝试使用一趟扫描实现吗?
先不考虑进阶,看如何实现。
/** * 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和slow,但过程也有区别。
我的操作:fast直接走到链表结尾,得出链表节点总数,再让slow后移num-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: 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异常。
可以回过头看[进阶]目录下代码完善。
(欢迎指正,转载标明出处)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。