力扣算法题—083删除排序链表中的重复数字

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

示例 1:

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

示例 2:

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

 1 #include "_000库函数.h"
 2 
 3 //这道题与上题的不同之处就是重复的数字不用全部删除，保留一个
 4 
 5 struct ListNode {
 6     int val;
 7     ListNode *next;
 8     ListNode(int x) : val(x), next(NULL) {}
 9 };
10 
11 //有释放的删除代码
12 class Solution {
13 public:
14     ListNode* deleteDuplicates(ListNode* head) {
15         //创建一个头结点
16         ListNode *p = new ListNode(0);
17         p->next = head;
18         head = p;
19         ListNode *q = p;
20         while (q && p) {
21             q = q->next;
22             while (q && q->next && q->val == q->next->val) {
23                 //一定的记得释放删除的数字
24                 ListNode *ptr = q;
25                 p->next = q->next;
26                 delete(ptr);
27                 ptr = NULL;
28                 q = p->next;
29             }
30             p = p->next;
31         }
32         return head->next;
33     }
34 };
35 
36 
37 //无释放的删除节点
38 class Solution {
39 public:
40     ListNode* deleteDuplicates(ListNode* head) {
41         //创建一个头结点
42         ListNode *p = new ListNode(0);
43         p->next = head;
44         head = p;
45         ListNode *q = p;
46         while (p->next) {
47             q = p->next;
48             while (q->next && q->val == q->next->val)
49                 q = q->next;
50             if (p->next != q)
51                 p->next = q;
52             p = p->next;
53         }
54         return head->next;
55     }
56 };
57 
58 
59 //使用递归
60 class Solution {
61 public:
62     ListNode* deleteDuplicates(ListNode* head) {
63         if (!head || !head->next) return head;
64         head->next = deleteDuplicates(head->next);
65         return (head->val == head->next->val) ? head->next : head;
66     }
67 };
68 
69 void T083() {
70     ListNode *head = new ListNode(0);
71     ListNode *p = head;
72     vector<int>v = { 1,2,3,4,4, 5, 5 };
73     for (auto a : v) {
74         ListNode *q = new ListNode(0);
75         q->val = a;
76         p->next = q;
77         p = q;
78     }
79     p = head->next;
80     while (p) {
81         cout << p->val << "->";
82         p = p->next;
83     }
84     cout << endl;
85     Solution s;
86     p = s.deleteDuplicates(head->next);
87     while (p) {
88         cout << p->val << "->";
89         p = p->next;
90     }
91     cout << endl;
92 }