?LeetCode刷題實(shí)戰(zhàn)82：刪除排序鏈表中的重復(fù)元素 II
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?刪除排序鏈表中的重復(fù)元素 II，我們先來看題面：
https://leetcode-cn.com/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
解題
解法
class?Solution?{
public:
????ListNode* deleteDuplicates(ListNode* head) {
??????????// 如果元素少于2個(gè)則直接返回
????????if?(head == nullptr || head->next == nullptr) return?head;
????????int cur = head->val;
??????????// 初始化
????????bool flag = false;
????????ListNode* ct = new?ListNode(0);
????????ListNode* pnt = ct;
????????head = head->next;
??????????// 遍歷元素
????????while?(head) {
????????????int hd = head->val;
???????????????// 判斷當(dāng)前元素與之前的元素是否相等
????????????if?(hd != cur) {
???????????????????// 之前的元素沒有出現(xiàn)重復(fù)
????????????????if?(!flag) {
???????????????????????// 把之前的元素存入鏈表
????????????????????pnt->next = new?ListNode(cur);
???????????????????????// 鏈表移動(dòng)
????????????????????pnt = pnt->next;
????????????????}else?flag = false;
???????????????????// 更新之前的元素
????????????????cur = hd;
????????????}else?flag = true;
????????????head = head->next;
????????}
??????????// 單獨(dú)處理最后一個(gè)元素
????????if?(!flag) pnt->next = new?ListNode(cur);
????????return?ct->next;
????}
};
class Solution:
????def deleteDuplicates(self, head: ListNode) -> ListNode:
????????# 創(chuàng)建一個(gè)新的元素放在鏈表頭部，這樣原本第一個(gè)元素就是頭指針的下一個(gè)元素了
????????node = ListNode()
????????node.next?= head
????????# pnt指向新創(chuàng)建的元素
????????pnt = node
????????
????????while?pnt.next?is?not None:
????????????# cur指向當(dāng)前位置的下一個(gè)位置
????????????# 我們要做的即判斷cur這個(gè)指針的元素是否重復(fù)
????????????cur = pnt.next
????????????if?cur.next?is?None:
????????????????break
?????????????
????????????# ptr指向cur的next
????????????ptr?= cur.next
????????????# 如果ptr和cur相等，那么出現(xiàn)重復(fù)，我們需要跳過所有相等的元素
????????????if?ptr?is?not None and?ptr.val == cur.val:
????????????????while?ptr?is?not None and?ptr.val == cur.val:
????????????????????ptr?= ptr.next
????????????????pnt.next?= ptr
????????????# 否則說明不重復(fù)，移動(dòng)pnt
????????????else:
????????????????pnt = pnt.next
????????????????
????????# 由于我們開始的時(shí)候人為添加了一個(gè)輔助元素
????????# 返回的時(shí)候要將它去除
????????return?node.next
總結(jié)
上期推文：