我制作了一種方法，可以按降序對兩個鏈表進行合并排序。我現在很難洗掉重復項。我見過一些洗掉重復的方法，但我想在我的mergesort方法中實作而不是創建一個新方法。mergesort為了洗掉輸出中的重復項，我應該在我的方法中添加什么？提前致謝！
預期產出
Input1: 90 90 20 30
Input2: 3 1 3 2 1 3
Output: 90 30 20 3 2 1
我的輸出
Input1: 90 90 20 30
Input2: 3 1 3 2 1 3
Output: 90 90 30 20 3 3 3 2 1 1
這是我按降序對兩個鏈表進行合并排序的方法。不確定這是否是處理重復的部分，但無論如何我已經標記了它。
public SLLNode<T> mergesort(SLLNode<T> n1, SLLNode<T> n2)
{
SLLNode<T> merged = null; // pointer for merged list
SLLNode<T> current = null; // head of merged list
if (n1 == null)
return n2;
if (n2 == null)
return n1;
int cmp = 0;
while (n1 != null && n2 != null)
{
cmp = n2.compareTo(n1);
if (merged == null) {
if (cmp < 0) {
merged = n1;
n1 = n1.next;
}
else if (cmp == 0)
{
// ****handles the duplicate****
}
else {
merged = n2;
n2 = n2.next;
}
current = merged; // points to head of merged list
}
else {
if (cmp < 0) {
merged.next = n1;
n1 = n1.next;
merged = merged.next;
}
else if (cmp == 0)
{
// ****handles the duplicate****
}
else {
merged.next = n2;
n2 = n2.next;
merged = merged.next;
}
}
}
// append the remaining nodes of the either list
if (n1 == null)
merged.next = n2;
else
merged.next = n1;
return current;
}
主要方法
System.out.println("Output:");
SLL<Integer> mergedList = new SLL<>();
mergedList.head = mergedList.mergesort(list1.head, list2.head);
mergedList.print(mergedList.head);
編輯
更新了歸并排序
public SLLNode<T> mergesort(SLLNode<T> n1, SLLNode<T> n2)
{
SLLNode<T> merged = null; // pointer for merged list
SLLNode<T> current = null; // head of merged list
if (n1 == null)
return n2;
if (n2 == null)
return n1;
int cmp = 0;
while (n1 != null && n2 != null)
{
cmp = n2.compareTo(n1);
if (merged == null)
{
if (cmp < 0)
{
merged = n1;
n1 = n1.next;
}
else
{
merged = n2;
n2 = n2.next;
}
current = merged; // points to head of merged list
}
else
{
if (cmp < 0)
{
if (merged.compareTo(n1) != 0)
{
merged.next = n1;
merged = merged.next;
}
n1 = n1.next;
}
else if (cmp == 0) // handles the duplicate
{
if (merged.compareTo(n1) != 0)
{
merged = n1;
merged = merged.next;
}
n1 = n1.next;
n2 = n2.next;
}
else
{
if (merged.compareTo(n2) != 0)
{
merged.next = n2;
merged = merged.next;
}
n2 = n2.next;
}
}
}
// append the remaining nodes of the either list
while (n2 != null)
{
if (merged.compareTo(n2) != 0)
{
merged.next = n2;
merged = merged.next;
}
n2 = n2.next;
}
while (n1 != null)
{
if (merged.compareTo(n1) != 0)
{
merged.next = n1;
merged = merged.next;
}
n1 = n1.next;
}
merged.next = null;
return current;
}
SLLNode 類
public class SLLNode <T extends Comparable<T>>
{
public T info;
public SLLNode<T> next;
public SLLNode(T el)
{
info = el;
next = null;
}
public SLLNode(T el, SLLNode<T> ptr)
{
info = el;
next = ptr;
}
public int compareTo(SLLNode<T> ptr)
{
return ((Comparable)info).compareTo(ptr.info);
}
public String toString()
{
return this.info.toString();
}
}
uj5u.com熱心網友回復：
僅當 2 個輸入串列已排序時，您的邏輯才會起作用。假設它們是，要洗掉代碼中的重復項，您可以merged在更新之前比較和（n1 或 n2）merged.next。merged.next = n1最后，您將不得不遍歷 n1 并與 n1 比較合并，而不是直接更新。您也可以使用equals來代替merged.compareTo(n1). 下面的代碼可以用在 else 塊中merged==null。else if (cmp == 0)不需要，merged == null因為當它們相等時設定 n1 或 n2 無關緊要。
if (cmp < 0) {
if (merged.compareTo(n1) != 0) {
merged.next = n1;
merged = merged.next;
}
n1 = n1.next;
} else if (cmp == 0) {
// ****handles the duplicate****
if (merged.compareTo(n1) != 0) {
merged = n1;
merged = merged.next;
}
n1 = n1.next;
n2 = n2.next;
} else {
if (merged.compareTo(n2) != 0) {
merged.next = n2;
merged = merged.next;
}
n2 = n2.next;
}
最后一部分可以替換為
while (n2 != null) {
if (merged.compareTo(n2) != 0) {
merged.next = n2;
merged = merged.next;
}
n2 = n2.next;
}
while (n1 != null) {
if (merged.compareTo(n1) != 0) {
merged.next = n1;
merged = merged.next;
}
n1 = n1.next;
}
merged.next = null;
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/456090.html
下一篇：開放世界假設有什么好處？