题目一：

　　给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list

思路：

　　注意考虑首尾节点等特殊情况，如果一个节点是None的，那么它不存在.val。

　　除非题目有声明，否则C++删除节点后应该回收资源，即使不回收内存可以通过测试，但应该养成好习惯！！！

C++实现：

 1 struct ListNode {
 2      int val;
 3      ListNode *next;
 4      ListNode(int x) : val(x), next(NULL) {}
 5  };
 6  
 7  class Solution {
 8  public:
 9      ListNode* deleteDuplicates(ListNode* head) {
10          ListNode *cur = head;
11          while (cur && cur->next) {
12              if (cur->val == cur->next->val) {  // 删除相等的节点后，直接进入循环判断条件
13                  ListNode *delNode = cur->next;
14                  cur->next = cur->next->next;
15                  delete delNode;  // 用delete删除节点
16              }
17              else
18                  cur = cur->next;
19          }
20          return head;
21      }
22  };

题目二：

　　给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:

输入: 1->1->1->2->3
输出: 2->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

思路：

　　使用快慢指针，快指针负责找重复的数据，慢指针负责跨过重复的数据将链表连接起来。

Python实现：

 1 class ListNode:
 2     def __init__(self, x):
 3         self.val = x
 4         self.next = None
 5 
 6 class Solution:
 7     def deleteDuplicates(self, head: ListNode) -> ListNode:
 8         tempHead = ListNode(None)  # 哨兵节点
 9         tempHead.next = head
10         slow = tempHead
11         fast = tempHead.next
12         while fast and fast.next:
13             if fast.val == fast.next.val:  # 如果快指针遇到重复值
14                 while fast and fast.next and fast.val == fast.next.val:
15                     fast = fast.next  # 继续移动快指针直到不再遇到重复值
16                 slow.next = fast.next  # 跳过重复值，将链表连接起来
17                 fast = fast.next  # 继续判断下一节点
18             else:
19                 slow = slow.next
20                 fast = fast.next
21         return tempHead.next

C++实现：

 1  struct ListNode {
 2      int val;
 3      ListNode *next;
 4      ListNode(int x) : val(x), next(NULL) {}
 5  };
 6  
 7 class Solution {
 8 public:
 9     ListNode* deleteDuplicates(ListNode* head) {
10         ListNode *tempNode = new ListNode(-1);
11         tempNode -> next = head;
12         ListNode *slow = tempNode;
13         ListNode *fast = tempNode -> next;
14 
15         while(fast && fast -> next) {
16             if(fast -> val == fast -> next -> val) {  // fast && fast->next已经被判断
17                 while(fast && fast -> next && fast -> val == fast -> next -> val) {
18                     ListNode *deleteNode = fast;  // 删除跳过的重复节点
19                     fast = fast -> next;
20                     delete deleteNode;
21                 }
22             slow -> next = fast -> next;
23             fast = fast -> next;  
24             }
25             else {
26                 slow = slow -> next;
27                 fast = fast -> next;
28             }
29         }
30         return tempNode -> next;
31     }
32 };

原文链接: https://www.cnblogs.com/kongzimengzixiaozhuzi/p/13221978.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/361456

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

删除排序链表中的重复元素（不完全删除 and 完全删除）

题目一：

思路：

C++实现：

题目二：

思路：

Python实现：

C++实现：

相关推荐