Fork me on GitHub

leetcode之83. 删除排序链表中的重复元素

发表于 | 分类于
字数统计 187 字 | 阅读时长 1 分钟

题目描述：

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

示例 1:

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

示例 2:

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

解题思路：

时间复杂度: $O(n)$, 空间复杂度: $O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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 || !head -> next) return head;
        ListNode *p = NULL, *q = NULL;
        p = head;
        q = head -> next;
        while( p -> next != NULL)
        {
           if(p -> val == q -> val)
            {
              p -> next = q -> next;
              delete q;
              q = p -> next;
            } 
            else
            {
                p = p -> next;
                q = q -> next;  
            }
        }
       
        return head;
    }
};