一、題目
??編寫代碼，移除未排序鏈表中的重復(fù)節(jié)點。保留最開始出現(xiàn)的節(jié)點。
??點擊此處跳轉(zhuǎn)題目。
示例1:
輸入：[1, 2, 3, 3, 2, 1]
輸出：[1, 2, 3]
示例2:
輸入：[1, 1, 1, 1, 2]
輸出：[1, 2]
提示：
- 鏈表長度在[0, 20000]范圍內(nèi)。
- 鏈表元素在[0, 20000]范圍內(nèi)。
進階：
- 如果不得使用臨時緩沖區(qū)，該怎么解決？
二、C# 題解
??使用哈希表記錄出現(xiàn)的數(shù)字，只需要一次遍歷即可：文章來源：http://www.zghlxwxcb.cn/news/detail-672282.html
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode RemoveDuplicateNodes(ListNode head) {
Dictionary<int, bool> map = new Dictionary<int, bool>();
ListNode p = head, q; // 雙指針，q 指向 p 的后一個元素
while (p != null) {
map[p.val] = true; // 記錄 p 指向的元素
q = p.next; // 更新 q
if (q == null) break;
int v = q.val; // 取出 p 指向的元素值
// 依據(jù) v 對 p 進行操作
if (map.ContainsKey(v)) p.next = q.next; // 重復(fù)值，則跳過 q
else p = q; // 非重復(fù)值，p 挪下一位
}
return head;
}
}
- 時間復(fù)雜度： O ( n ) O(n) O(n)。
- 空間復(fù)雜度： O ( n ) O(n) O(n)。
如果不使用臨時緩沖區(qū)，則需要每個元素依次檢查，進行多次遍歷：文章來源地址http://www.zghlxwxcb.cn/news/detail-672282.html
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode RemoveDuplicateNodes(ListNode head) {
ListNode p = head, q; // 雙指針
while (p != null) {
int v = p.val; // 取出 p 指向元素的值
q = p; // q = p 代替 p進行遍歷
// 出現(xiàn) v 則刪，否則跳到下一個
while (q.next != null) {
if (q.next.val == v) q.next = q.next.next;
else q = q.next;
}
p = p.next; // 更新 p
}
return head;
}
}
- 時間復(fù)雜度： O ( n 2 ) O(n^2) O(n2)。
- 空間復(fù)雜度： O ( 1 ) O(1) O(1)。
到了這里，關(guān)于LeetCode 面試題 02.01. 移除重復(fù)節(jié)點的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
