网站开发技术入股协议,html5 个人网站模板,最专业的企业营销型网站建设,自己做的网站怎么接入银联支付Leetcode 237. 删除链表中的节点
问题#xff1a;有一个单链表的head#xff0c;我们想删除它其中的一个节点node。给你一个需要删除的节点 node 。你将 无法访问 第一个节点head。链表的所有值都是唯一的#xff0c;并且保证给定的节点 node不是链表中的最后一个节点。删除…Leetcode 237. 删除链表中的节点
问题有一个单链表的head我们想删除它其中的一个节点node。给你一个需要删除的节点 node 。你将 无法访问 第一个节点head。链表的所有值都是唯一的并且保证给定的节点 node不是链表中的最后一个节点。删除给定的节点。注意删除节点并不是指从内存中删除它。这里的意思是
给定节点的值不应该存在于链表中。链表中的节点数应该减少 1。node 前面的所有值顺序相同。node 后面的所有值顺序相同。
自定义测试
对于输入你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点而应该是链表中的一个实际节点。我们将构建链表并将节点传递给你的函数。输出将是调用你函数后的整个链表。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
算法把 node 的下一个结点复制过来然后 delete 下一个结点。
代码
class Solution {
public:void deleteNode(ListNode* node) {*node *node-next;}
};
class Solution {
public:void deleteNode(ListNode* node) {auto nxt node-next;*node *nxt;delete nxt;}
}; Leetcode 19. 删除链表的倒数第 N 个结点
问题给你一个链表删除链表的倒数第 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) {}* };*/
算法设置哨兵结点 dummy 双指针。让右指针 right 先向右走 n 步然后左右指针一起向右走当右指针指向最后一个结点时左指针 left 刚好指向倒数第 n 个。
代码
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode dummy{0,head};// 哨兵结点(当头结点有可能被删除时设置)auto left dummy,right dummy;// 双指针while(n--) right right-next;// 让右指针right先走n步while(right-next){// 左右指针一起走left left-next;right right-next;}auto nxt left-next;left-next left-next-next;delete nxt;return dummy.next;}
}; Leetcode 83. 删除排序链表中的重复元素
问题给定一个已排序的链表的头head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。 /*** 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* deleteDuplicates(ListNode* head) {if(head nullptr) return nullptr;auto cur head;while(cur-next){if(cur-next-val cur-val){auto nxt cur-next;cur-next nxt-next;delete nxt;}else cur cur-next;}return head;}
}; Leetcode 82. 删除排序链表中的重复元素 II
问题给定一个已排序的链表的头head 删除原始链表中所有重复数字的节点只留下不同的数字 。返回已排序的链表 。 /*** 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) {}* };*/
算法遇到相同元素值的结点全部删除。新建变量 val 存储重复出现的元素值一旦有结点的值与变量 val 相等则删除。
代码
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode dummy(0,head);auto cur dummy;while(cur-next cur-next-next){int val cur-next-val;if(val cur-next-next-val){while(cur-next cur-next-val val){// 只要一样就一直删除auto nxt cur-next;cur-next nxt-next;delete nxt;}}else cur cur-next;// 删除完就跳到下一个位置}return dummy.next;}
};
