Leetcode 237.19.83.82 删除链表重复结点 C++实现
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;}
};