许昌网站制作公司,枣庄网站建设,新开传奇网站发布网孞,移动广告公司网站建设题目的意思很简单#xff0c;就是删除一个链表倒数第N个节点。 需要用到链表的标准操作#xff1a;快慢指针。 我们让一个快指针先指向第N个元素#xff0c;这个时候快指针总比慢指针领先N个元素#xff0c;等到快指针指向链表尾部的时候慢指针就指向需要删除的元素。 之前…题目的意思很简单就是删除一个链表倒数第N个节点。 需要用到链表的标准操作快慢指针。 我们让一个快指针先指向第N个元素这个时候快指针总比慢指针领先N个元素等到快指针指向链表尾部的时候慢指针就指向需要删除的元素。 之前已经用了几次了比如空间复杂度O(1)O(1)O(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 new ListNode(0, head);ListNode *first head;for(int i0; in; i) first first-next;ListNode *second dummy;while(first){first first-next;second second-next;}second-next second-next-next;head dummy-next;delete dummy;return head;}
};之前在看对Linus的采访的时候学到一种新的操作链表的方法那就是二级指针。 我们对于内存块的控制都是通过指针进行的因此我们控制链表的核心就是控制指针的值。但是只使用一级指针是无法直接改变指针的值的因为我们会对指向某个内存块的指针进行一次复制而无法对我们需要返回的那个指针进行修改。为了修改那个指针我们一般需要保存前驱节点来得到指向对应内存块的指针。
但是使用二级指针以后就可以避免这个问题因为使用二级指针的话我们是直接对原数据中指向内存块的指针进行操作的。这样就不需要前驱节点。
/*** 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;for(int i0; in; i) first first-next;ListNode **second head;while(first){first first-next;second (*second)-next;}*second (*second)-next;return head;}
};
