每日一道 LeetCode (18)：刪除排序鏈表中的重復(fù)元素

?

每天 3 分鐘，走上算法的逆襲之路。

?

前文合集

每日一道 LeetCode 前文合集

代碼倉庫

GitHub：https://github.com/meteor1993/LeetCode

Gitee：https://gitee.com/inwsy/LeetCode

題目：刪除排序鏈表中的重復(fù)元素

題目來源：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

給定一個排序鏈表，刪除所有重復(fù)的元素，使得每個元素只出現(xiàn)一次。

示例?1:

輸入:?1->1->2
輸出:?1->2

示例?2:

輸入:?1->1->2->3->3
輸出:?1->2->3

解題思路

連續(xù)被數(shù)學(xué)題虐了兩天，今天終于能看到一道正常的，普通智商可以解開的算法題了。

我太難了，每天晚上都被數(shù)學(xué)題虐的死去活來，一度讓我精神恍惚，仿佛回到高三那一年。

題目要求給一個排序鏈表去重，這個鏈表已經(jīng)是排好序的了，那么去重這件事兒就很簡單了，只要重復(fù)，必定鏈表上的兩個元素是相鄰的，所以只需要在一個循環(huán)中判斷相鄰 n 和 n + 1 個元素是否相等就好，如果相等的話，那么元素 n 上的指針直接指向 n + 2 ，進(jìn)行下一次循環(huán)，判斷這兩個元素是否相等。

public?ListNode?deleteDuplicates(ListNode?head)?{
????ListNode?current?=?head;
????while?(current?!=?null?&&?current.next?!=?null)?{
????????if?(current.val?==?current.next.val)?{
????????????current.next?=?current.next.next;
????????}?else?{
????????????current?=?current.next;
????????}
????}
????return?head;
}

上面這種算法稍稍有點小問題，從示意圖上可以看到， n + 1 這個元素的指針還指向了 n + 2 ，如果鏈表比較大，會產(chǎn)生很多的 「野指針」 ，這段代碼稍微改一下，我們把刪掉不用的元素置空：

public?ListNode?deleteDuplicates_1(ListNode?head)?{
????ListNode?current?=?head;
????while?(current?!=?null?&&?current.next?!=?null)?{
????????if?(current.val?==?current.next.val)?{
????????????ListNode?node?=?current.next;
????????????current.next?=?node.next;
????????????node.next?=?null;
????????}?else?{
????????????current?=?current.next;
????????}
????}
????return?head;
}

和第一種寫法耗時維持一致，這個很正常，我們只是清除掉了不在使用的元素，并沒有優(yōu)化尋找方案，整體的時間復(fù)雜度還是保持了 O(n) 。