list元素求和_LeetCode刷题实战82：删除排序链表中的重复元素 II

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做删除排序链表中的重复元素 II，我们先来看题面：

https://leetcode-/problems/remove-duplicates-from-sorted-list-ii/

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

题意

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。样例

示例 1:

输入: 1->2->3->3->4->4->5

输出: 1->2->5

示例 2:

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

输出: 2->3

解题

/techflow/p/13235840.html

解法

前面说了这题的质量很高，这题是属于典型的解法赤裸裸，但是很多人就是写不出来的题，非常考察基本功。适合用在校招面试当中，如果我有幸去面试校招生， 我可能会选这道题。不存在算法会不会的问题，写不出来一定是基本功不够扎实。链表已经有序了，那么相同的元素必然会排在一起，我们只需要将它们移除就可以了。但是说起来简单，要在链表当中实现并不容易。难点主要有两个，一个是链表增删节点的操作很多人不熟悉，尤其是像是C++这样的语言涉及指针，可能更不容易。另外一个难点就在题意当中，我们要做的不是去重，而是要所有重复的元素全部删除。看起来似乎和去重没什么差别， 如果你真这么想，并且着手去实现，那么几乎可以肯定一定会遇到问题。因为链表是单向的，假设你当前的指针是cur，当你发现cur这个指针的元素存在重复的时候，你需要连当前这个节点一起删除。我们都知道，单向链表是不能走回头路的，而删除节点，必须要用到前一个节点的指针。再加上判断元素重复需要用到的指针，会需要我们同时维护多个指针，增加代码的编码难度。针对这个问题，我们有两种解决思路。第一种是我们不在原链表上处理，而是创建一个新的链表进行返回。所以我们要做的就不是删除元素，而是插入元素，只有发现当前元素不存在重复的时候才会插入链表。最后返回的也是一个全新的链表。这当然是可以的，也是没有问题了，我第一次做这道题就是采取的这种措施。相比之下， 这种方法会容易一些，因为我们不需要判断太多的指针和位置，我贴一下当时的代码：

classSolution{public:

ListNode* deleteDuplicates(ListNode* head) {// 如果元素少于2个则直接返回if(head == nullptr || head->next == nullptr) returnhead;

int cur = head->val;// 初始化

bool flag = false;

ListNode* ct = newListNode(0);

ListNode* pnt = ct;

head = head->next;// 遍历元素while(head) {

int hd = head->val;// 判断当前元素与之前的元素是否相等if(hd != cur) {// 之前的元素没有出现重复if(!flag) {// 把之前的元素存入链表

pnt->next = newListNode(cur);// 链表移动

pnt = pnt->next;

}elseflag = false;// 更新之前的元素

cur = hd;

}elseflag = true;

head = head->next;

}// 单独处理最后一个元素if(!flag) pnt->next = newListNode(cur);returnct->next;

}

};

虽然题目当中没有对解法做出限制，也没有规定我们必须要在原链表上进行处理，但是这种创建新链表的方法终归有绕开问题的嫌疑。所以我们还有第二种解法，就是直面问题，我们维护多个指针，判断当前位置的下一个元素是否构成重复。如果重复，则删除掉重复的部分。正如我们之前所说的那样，在单向链表当中很难删除当前元素，所以我们判断下一个元素是否会构成重复。如果重复的话，进行删除要可行许多。这样也有一个问题就是，有可能链表的第一个元素就是重复的，我们没有办法找到第一个元素的上一个元素。针对这个问题，我们采用的方法是人为给它创造一个元素放在首元素之前。这样我们整个流程就可以串起来了，唯一的难点就是编码了。我们仔细一些，写出代码还是可以的：

class Solution:

def deleteDuplicates(self, head: ListNode) -> ListNode:

# 创建一个新的元素放在链表头部，这样原本第一个元素就是头指针的下一个元素了

node = ListNode()

node.next= head

# pnt指向新创建的元素

pnt = nodewhilepnt.nextisnot None:

# cur指向当前位置的下一个位置

# 我们要做的即判断cur这个指针的元素是否重复

cur = pnt.nextifcur.nextisNone:break

# ptr指向cur的nextptr= cur.next

# 如果ptr和cur相等，那么出现重复，我们需要跳过所有相等的元素ifptrisnot None andptr.val == cur.val:whileptrisnot None andptr.val == cur.val:ptr= ptr.next

pnt.next= ptr

# 否则说明不重复，移动pntelse:

pnt = pnt.next

# 由于我们开始的时候人为添加了一个辅助元素

# 返回的时候要将它去除returnnode.next

总结

这道题的算法很简单，我想大部分人都能想出解法来，但是要将解法实现并不太容易。这当中用到了很多小技巧，比如我们认为创建了一个新的头结点，比如我们将删除当前元素转化成了删除下一个元素等等。这些技巧虽然算不上什么，但是灵活使用，可以大大降低我们编码的复杂度，也正是因为这一点，这题的质量非常高，值得一做。很多人非常讨厌涉及链表的问题，觉得链表很难操作，容易写错，但实际上这是基本功的很重要的一部分。很多公司喜欢考察候选人的基本功，提升这方面的能力对于我们应聘或者是工作非常有帮助。好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

上期推文：

LeetCode40-60题汇总，速度收藏！LeetCode刷题实战61：旋转链表LeetCode刷题实战62：不同路径LeetCode刷题实战63：不同路径 IILeetCode刷题实战64：最小路径和LeetCode刷题实战66：加一LeetCode刷题实战67：二进制求和LeetCode刷题实战68：文本左右对齐LeetCode刷题实战69：x 的平方根LeetCode刷题实战70：爬楼梯LeetCode刷题实战71：简化路径LeetCode刷题实战72：编辑距离LeetCode刷题实战73：矩阵置零LeetCode刷题实战74：搜索二维矩阵LeetCode刷题实战75：颜色分类LeetCode刷题实战76：最小覆盖子串LeetCode刷题实战77：组合LeetCode刷题实战78：子集LeetCode刷题实战79：单词搜索

如果觉得《list元素求和_LeetCode刷题实战82：删除排序链表中的重复元素 II》对你有帮助，请点赞、收藏，并留下你的观点哦！