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;}
};