Merge Two Sorted Linked Lists And Remove Duplicates

"You

Example 1

Input: list1 = 1 → 2 → 4 , list2 = 1 → 3 → 4 Output: 1 → 2 → 3 → 4

Example 2

Input: list1 = [], list2 = [] Output: []

Example 3

Input: list1 = [], list2 = [0] Output: [0]

Solution 1 - Merge two sorted lists, then remove duplicates
Solution 2 - Remove duplicates while merging the lists

Solution 1 - 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.

Java

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.

Solution 2 - 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.

Java

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.

Above examples source code can be found at GitHub link for Java code and JUnit tests can be found at GitHub link for Unit tests code

Merge Two Sorted Linked Lists And Remove Duplicates

Example 1

Example 2

Example 3

Solution 1 - Merge two sorted lists, then remove duplicates

Complexity Analysis:

Solution 2 - Remove duplicates while merging the lists

Complexity Analysis:

Similar Articles