在合并排序的链表中删除重复项

Question

我制作了一种方法，可以按降序合并对两个链表进行排序。我现在很难删除重复项。我已经看到一些删除重复的方法，但我想在我的 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 Class

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();
    }
}

Answer 1

只有当 2 个输入列表已经排序时，您的逻辑才有效。假设它们是，要删除代码中的重复项，您可以在更新 merged.next 之前比较 merged 和（n1 或 n2）。同样在最后而不是直接更新 merged.next = n1 你将不得不遍历 n1 并与 n1 合并进行比较。您也可以使用 equals 而不是 merged.compareTo(n1)。下面的代码可以用在 merged==null 的 else 块中。当 merged == null 时不需要 else if (cmp == 0)，因为当它们相等时设置 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.next = 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;

在合并排序的链表中删除重复项

Remove duplicate in merge sort of linked lists

java

generics

mergesort

linked-list

nodes

编辑