力扣算法题—082删除排序链表中的重复元素2

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

示例 1:

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

示例 2:

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

  1 #include "_000库函数.h"
  2 
  3 
  4 struct ListNode {
  5     int val;
  6     ListNode *next;
  7     ListNode(int x) : val(x), next(NULL) {}
  8 };
  9 
 10 
 11 //又是无头结点的链表！！！
 12 //还有，哪个数字重复了，就将他全部删除！！
 13 class Solution {
 14 public:
 15     ListNode* deleteDuplicates(ListNode* head) {
 16         //创建一个头结点
 17         ListNode *p = new ListNode(0);
 18         p->next = head;
 19         head = p;
 20         ListNode *q = p;
 21         int flag = 0;//用来标记重复数字
 22         while (q && p) {
 23             q = q->next;
 24             while (q && q->next && q->val == q->next->val) {
 25                 //一定的记得释放删除的数字
 26                 ListNode *ptr = q;
 27                 p->next = q->next;
 28                 delete(ptr);
 29                 ptr = NULL;
 30                 q = p->next;
 31                 flag = 1;
 32             }
 33             if (flag) {//删除最后一个重复了的数字
 34                 ListNode *ptr = q;
 35                 p->next = q->next;
 36                 delete(ptr);
 37                 ptr = NULL;
 38                 q = p;
 39                 flag = 0;
 40             }
 41             else
 42                 p = p->next;
 43         }
 44         return head->next;
 45     }
 46 };
 47 
 48 //不释放删除的节点，我不建议，但好多博客是这样写的
 49 class Solution {
 50 public:
 51     ListNode* deleteDuplicates(ListNode* head) {
 52         //创建一个头结点
 53         ListNode *p = new ListNode(0);
 54         p->next = head;
 55         head = p;
 56         ListNode *q = p;
 57         while (p->next) {
 58             q = p->next;
 59             while (q->next && q->val == q->next->val)
 60                 q = q->next;
 61             if (p->next != q)
 62                 p->next = q->next;
 63             else
 64                 p = p->next;
 65         }
 66         return head->next;
 67     }
 68 };
 69 
 70 
 71 
 72 //使用递归，不使用while
 73 
 74 class Solution {
 75 public:
 76     ListNode *deleteDuplicates(ListNode *head) {
 77         if (!head) return head;
 78         if (head->next && head->val == head->next->val) {
 79             while (head->next && head->val == head->next->val) {
 80                 head = head->next;
 81             }
 82             return deleteDuplicates(head->next);
 83         }
 84         head->next = deleteDuplicates(head->next);
 85         return head;
 86     }
 87 };
 88 void T082() {
 89     ListNode *head = new ListNode(0);
 90     ListNode *p = head;
 91     vector<int>v = { 1,2,3,4,4, 5, 5};
 92     for (auto a : v) {
 93         ListNode *q = new ListNode(0);
 94         q->val = a;
 95         p->next = q;
 96         p = q;
 97     }
 98     p = head->next;
 99     while (p) {
100         cout << p->val << "->";
101         p = p->next;
102     }
103     cout << endl;
104     Solution s;
105     p = s.deleteDuplicates(head->next);
106     while (p) {
107         cout << p->val << "->";
108         p = p->next;
109     }
110     cout << endl;
111 }