【LeetCode】83. 删除排序链表中的重复元素

【题目描述】

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

示例 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

【解题思路】

注意此题与【LeetCode】02.01. 移除重复节点的区别，此题中链表为有序链表；

因而可以进行优化，遍历链表一遍，逐个将当前节点与其下一个节点比较，如果相等，则删除其下一个节点，只需遍历一遍即可。

【提交代码】

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 
 9 #if 0
10 struct ListNode* deleteDuplicates(struct ListNode* head){
11     struct ListNode *p;
12     struct ListNode *pre;
13     struct ListNode *cur;
14     int val;
15 
16     p = head;
17 
18     while( p != NULL )
19     {
20         val = p->val;
21 
22         pre = p;
23         cur = p->next;
24         while( cur != NULL )
25         {
26             if( cur->val == val ) // 删除当前的节点
27             {
28                 pre->next = cur->next; // pre的next指向cur的next，相当于断开了cur，即意为删除
29             }
30             else
31             {
32                 pre = pre->next;
33             }
34             cur = cur->next;
35         }
36 
37         p = p->next;
38     }
39 
40     return head;
41 }
42 #endif
43 // 由于数组本身有序，可以利用这个特性，遍历一遍即可；
44 struct ListNode* deleteDuplicates(struct ListNode* head){
45     struct ListNode *cur;
46 
47     cur = head;
48 
49     while( cur != NULL && cur->next != NULL )
50     {
51         if( cur->val == cur->next->val )
52         {
53             cur->next = cur->next->next;
54         }
55         else
56         {
57             cur = cur->next;
58         }
59     }
60     return head;
61 }