题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
解题思路
方法一：Map
1、思路：遍历一遍链表，把结点值以及其出现的次数作为键值对保存，然后再次遍历链表，用不重复的结点重构链表。
2、代码：
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead){if (!pHead) return nullptr;ListNode *tmp = pHead;map<int, int> mp;//哨兵结点ListNode *head = new ListNode(-1);while (tmp) {mp[tmp->val]++;tmp = tmp->next;}tmp = pHead;ListNode *cur = head;while (tmp) {if (mp[tmp->val] == 1) {cur->next = tmp;cur = tmp;}tmp = tmp->next;}cur->next = nullptr;return head->next;}
};3、复杂度：
时间复杂度：O(n)；
空间复杂度：O(n)。
方法二：双指针
1、思路：设置两个指针，遍历链表，若有重复结点（假设为X），前一个指针始终指向X的前一个结点，后一个指针始终指向最后一个X，然后改变指针，剔除该重复结点，继续遍历链表。
2、代码：
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead){if (!pHead) return nullptr;ListNode *head = new ListNode(-1);head->next = pHead;ListNode *pre = head, *cur = pHead;while (cur) {if (cur->next && (cur->val == cur->next->val)) {cur = cur->next;while (cur->next && (cur->val == cur->next->val)) {cur = cur->next;}pre->next = cur->next;cur = cur->next;} else {pre = cur;cur = cur->next;}}return head->next;}
};3、复杂度：
时间复杂度：O(n)；
空间复杂度：O(1)。