I have made a method that merge sorts two linked lists in descending order. I am now having difficulty in removing duplicates. I have seen some remove duplicate methods but I want to implement in within my mergesort method and not create a new method. What should I add in my mergesort method in order to remove the duplicates in the output? Thanks in advance!
Expected Output
Input1: 90 90 20 30
Input2: 3 1 3 2 1 3
Output: 90 30 20 3 2 1
My Output
Input1: 90 90 20 30
Input2: 3 1 3 2 1 3
Output: 90 90 30 20 3 3 3 2 1 1
This is my method to merge sort the two linked lists in descending order. Not sure if this is the part where the duplication is being handled but I have marked it anyway.
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;
}
Main Method
System.out.println("Output:");
SLL<Integer> mergedList = new SLL<>();
mergedList.head = mergedList.mergesort(list1.head, list2.head);
mergedList.print(mergedList.head);
Edit
Updated mergesort
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 this.info.compareTo(ptr.info);
}
public String toString()
{
return this.info.toString();
}
}
CodePudding user response：
Your logic will only work if the 2 input lists are already sorted. Assuming they are, to remove duplicates in your code you can compare merged and (n1 or n2) before updating merged.next. Also in the end rather than directly updating merged.next = n1 you will have to traverse through n1 and compare merged with n1. You can also used equals instead of merged.compareTo(n1).
The below code can be used in the else block of merged==null. else if (cmp == 0) is not required when merged == null as it does not matter if n1 or n2 is set when they are equal.
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;
}
The last part can be replaced with
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;