题目链接：83. 删除排序链表中的重复元素

题解：

与上一个题类似，链表操作！

题目简述：

给定一个有序链表，将有重复的元素删掉（有重复的保留一个）

与上一题全删有点不同

题解：

由于重复元素可以保留一个，所以第一个节点处理和后面一样，所以这里不需要建立虚拟头结点了！

思路：

  • 判断后面节点和当前已扫描节点形成的链表的最后一个节点是否相同
  • 若相同，则跳过当前节点，指向该节点下一个节点l->next = l->next->next
  • 若不同，则指向当前节点，即l = l->next

相同时，保证末尾l不动，next移动，不同时，l直接移到不同的节点。

时间复杂度：O(n)

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        auto l = head;
        while(l->next){
            if(l->val == l->next->val) l->next = l->next->next;
            else l = l->next;
        }
        return head;
    }
};