我只是在練習(xí)我的數(shù)據(jù)結(jié)構(gòu)并嘗試制作一種方法來從單向鏈表中刪除重復(fù)項。這就是我所擁有的： void removeDup() { Node temp = head; Node cur = null; String s = ""; while(temp!=null) { cur = temp; if(!s.contains(temp.data + "")) { s += temp.data + ""; } else { cur.next = temp.next; } temp = temp.next; } }執(zhí)行此方法后打印鏈表顯示沒有變化。我相信這是因為我沒有正確地將前一個鏈接鏈接到當(dāng)前鏈接的 .next 值，但在我看來一切都是正確的。我調(diào)試它，它似乎正確刪除了節(jié)點(diǎn)，但是當(dāng)我之后打印出鏈表時仍然出現(xiàn)重復(fù)的節(jié)點(diǎn)。建議？
3 回答
RISEBY
TA貢獻(xiàn)1856條經(jīng)驗 獲得超5個贊
代碼是從https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/復(fù)制的：
方法 1 - 蠻力，找到所有成對的兩個節(jié)點(diǎn)，看看它們是否具有相同的值，不確定調(diào)用 System.gc() 是否是一個好主意：
/* Function to remove duplicates from an
unsorted linked list */
void remove_duplicates() {
Node ptr1 = null, ptr2 = null, dup = null;
ptr1 = head;
/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;
/* Compare the picked element with rest
of the elements */
while (ptr2.next != null) {
/* If duplicate then delete it */
if (ptr1.data == ptr2.next.data) {
/* sequence of steps is important here */
dup = ptr2.next;
ptr2.next = ptr2.next.next;
System.gc();
} else /* This is tricky */ {
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}
方法二——使用hashset幫助檢測重復(fù)，我個人更喜歡這個方法：
/* Function to remove duplicates from a
unsorted linked list */
static void removeDuplicate(node head)
{
// Hash to store seen values, changed a little to compile for Java 8
HashSet<Integer> hs = new HashSet<Integer>();
/* Pick elements one by one */
node current = head;
node prev = null;
while (current != null)
{
int curval = current.val;
// If current value is seen before
if (hs.contains(curval)) {
prev.next = current.next;
} else {
hs.add(curval);
prev = current;
}
current = current.next;
}
}
撒科打諢
TA貢獻(xiàn)1934條經(jīng)驗 獲得超2個贊
cur.next = temp.next不會改變?nèi)魏螙|西。使用例如 Java 8：
new LinkedList<>(Arrays.asList(1,2,1,3)).stream().distinct().collect(Collectors.toList());
或者
new LinkedHashSet<>(new LinkedList<>(Arrays.asList(1,2,1,3)))
另見https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list
鳳凰求蠱
TA貢獻(xiàn)1825條經(jīng)驗 獲得超4個贊
首先，我認(rèn)為您選擇將所有以前的東西保存在一個字符串中可能是一個壞主意。
例如，如果你給它提供了一個帶有 {x,y, xy} 的列表。第三個項目將被檢測為重復(fù)。幾個簡單的替代方法。
將以前的值保存在某個集合中/為每個元素檢查是否有其他等效項。排序一切，然后檢查人們的鄰居。
你設(shè)置 cur = temp; 在循環(huán)的頂部，因此執(zhí)行 cur.next = temp.next; 之后什么也不做。不要在循環(huán)的頂部設(shè)置 cur 等于 temp 或者只是在之后更改它。
添加回答
舉報
0/150
提交
取消