剑指Offer（五十六）-- 删除链表中重复的元素
Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
示例1
输入
{1,2,3,3,4,4,5}
返回值
{1,2,5}
节点的数据结构如下：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
思路以及解答
第一种做法是借助额外的空间，使用了LinkedHashMap,先遍历一次，将里面的元素以及出现的次数，记录下来，key是出现的元素，value是出现的次数，只要出现超过一次，就将其value置为-1。
再次遍历LinkedHashMap里面的元素，取出value不为-1的元素，也就是出现一次的元素，拼接成为链表。实现代码如下：
public ListNode deleteDuplication(ListNode pHead) {
HashMap<Integer,Integer> maps = new LinkedHashMap<>();
if (pHead != null) {
// 遍历添加到set中
while (pHead != null) {
if (!maps.containsKey(pHead.val)) {
maps.put(pHead.val,1);
}else{
maps.put(pHead.val,-1);
}
pHead = pHead.next;
}
ListNode listNode = new ListNode(-1);
ListNode temp = listNode;
for (Map.Entry<Integer,Integer> entry: maps.entrySet()) {
if(entry.getValue()==1){
temp.next = new ListNode(entry.getKey());
temp = temp.next;
}
}
return listNode.next;
}
return null;
}
上面的做法借助了额外的空间，空间复杂度为O(n)，时间复杂度为O(2n)，也就是O(n)。
当然，还有另外一种做法，就是不需要借助额外的空间，也就是原地删除，对比前后两个元素，如果相同的情况下，接着遍历后面的元素，直到元素不相等的时候，将前面的指针指向最后一个相同的元素的后面，相当于跳过了相同的元素。
public ListNode deleteDuplication(ListNode pHead) {
ListNode head = new ListNode(-1);
head.next = pHead;
// 上一个元素指针为pre
ListNode pre = head, cur = pHead;
while (cur!=null) {
if (cur.next!=null && cur.val == cur.next.val) {
cur = cur.next;
while (cur.next!=null && cur.val == cur.next.val) {
cur = cur.next;
}
cur = cur.next;
pre.next = cur;
}
else {
pre = cur;
cur = cur.next;
}
}
return head.next;
}
空间复杂度为O(1)，没有借助额外的空间，时间复杂度为O(n)，只遍历了一次链表。
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。
平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -
腾讯云开发者
