Merge two sorted lists, then remove duplicates

• As a first step, we will merge two lists using same exact steps used in Merge Two Sorted Lists.
• Once the lists are merged, then the next step is to remove duplicates from it using below steps.

• The idea here is to loop through list elements and if current element and next element are same, then set current node's next element as the next's next element, by doing this we are skipping current node's next element.
• Create a temporary variable ListNode current and assign the list to it. The purpose of this variable is to hold current node that we are iterating through.
• Run a while loop until the end of list. Now check if node value is equal to next node's value, if they are same then set current node's next node as next node's next current.next = current.next.next, otherwise set the current = current.next to continue with next node.

public class MergeTwoSortedListsRemoveDuplicates { static class ListNode { int element; ListNode next; public ListNode(int element) { this.element = element; } } public ListNode mergeAndRemoveDuplicates(ListNode list1, ListNode list2) { ListNode result = merge(list1, list2); removeDuplicates(result); return result; } public ListNode merge(ListNode list1, ListNode list2) { ListNode result = new ListNode(0); ListNode temp = result; while(list1!=null || list2!=null) { if(list1 == null) { temp.next = list2; break; } if(list2 == null){ temp.next = list1; break; } if(list1.element <= list2.element) { temp.next = new ListNode(list1.element); list1 = list1.next; } else if (list1.element > list2.element) { temp.next = new ListNode(list2.element); list2 = list2.next; } temp = temp.next; } return result.next; } public void removeDuplicates(ListNode linkedList) { ListNode current = linkedList; // pointer to current head while(current.next != null) { if(current.element == current.next.element) { current.next = current.next.next; } else { current = current.next; } } } }

Complexity Analysis:

Above code runs in O(m + n) time complexity where m is the size of the input list1 and n is the size of the input list2, as we are looping through the input lists one time for merge process and one more time for removing duplicates. Space complexity is O(n) that is taken by the result list.

Remove duplicates while merging the lists

• Create a new ListNode with dummy node as head, call it as result. We are going to attach input list's elements to this list and finally return answer by removing this dummy head.
• Create another temporary ListNode variable to hold the tail of the resultant list, so that next node comes in order from input lists will be attached to this.
  Initialize this with result from above step as that is the current tail.
• Run a while loop until both input lists are not null. Now check which node value is less among two input lists, compare this node value with temp node value, if they are not same then add this node to tail of temp node, otherwise skip it.
• Finally return result.next, this will remove the dummy head created in step 1 and return the rest.

public class MergeTwoSortedListsRemoveDuplicates { static class ListNode { int element; ListNode next; public ListNode(int element) { this.element = element; } } public ListNode removeDuplicatesWhileMerging(ListNode list1, ListNode list2) { ListNode result = new ListNode(0);// create a new ListNode with a dummy head ListNode temp = result; int counter=0; while(list1 != null || list2 != null) { if( (list1 != null && list2 != null && list1.element <= list2.element) || (list2 == null)) { if(counter == 0 || (list1!=null && temp.element != list1.element)) { temp.next = new ListNode(list1.element); } list1 = list1.next; } else if( (list1 != null && list2 != null && list1.element > list2.element) || (list1 == null)) { if(counter == 0 || (list2 != null && temp.element != list2.element)) { temp.next = new ListNode(list2.element); } list2 = list2.next; } counter++; if(temp.next != null) { temp = temp.next; } } return result.next; } }

Complexity Analysis:

Above code runs in O(m + n) time complexity where m is the size of the input list1 and n is the size of the input list2, as we are looping through the input lists only once. Space complexity is O(n) that is taken by the result list.