Is there a cleaner or more efficient way to remove all values in a sorted linked list that appear in another sorted linked list?

Question

I'm currently doing some practice problems for a course I'll be taking in the fall and I ran into this question:

Write a method removeAll that could be added to the LinkedIntList class. The method should efficiently remove from a sorted list of integers all values appearing in a second sorted list of integers. For example, suppose LinkedIntList variables list1 and list2 refer to the following lists:

list1: [1, 3, 5, 7]

list2: [1, 2, 3, 4, 5]

If the call list1.removeAll(list2) is made, the lists should store the following values after the call:

list1: [7]

list2: [1, 2, 3, 4, 5]

Both lists are guaranteed to be in sorted (non-decreasing) order, although there might be duplicates in either list. Because the lists are sorted you can solve this problem very efficiently with a single pass through the data. Your solution is required to run in O(M + N) time where M and N are the lengths of the two lists.

You may not call any other methods of the class to solve this problem, you may not construct any new nodes, and you may not use any auxiliary data structures to solve this problem (such as an array, ArrayList, Queue, String, etc.). You also may not change any data fields of the nodes. You must solve this problem by rearranging the links of the lists.

In order to solve this problem, there's a custom LinkedIntList and ListNode class that's provided.

public class LinkedIntList {
    private ListNode front;    // head of the list
    ...
}

public class ListNode {
    public int data;    // value stored in this node of the list
    public ListNode next;    // reference to next node in the list (null if end of list)
    ...
}

I solved this question in O(M + N) time in one pass. However, I'm wondering if there's any way to solve this question more efficiently. I have a nested if-else block within an if-statement and I think it could be cleaned up. I have included my code below.

public void removeAll(LinkedIntList list2) {
    if (this.front != null && list2.front != null) {
        // iterators for the list to remove values from
        ListNode prev = null;
        ListNode current = this.front;

        // iterator for the list where values from list1 may appear
        ListNode list2Current = list2.front;

        // reference to the front of list1
        ListNode head = current;

        while (current != null && list2Current != null) {

            while (current != null && current.data < list2Current.data) {
                prev = current;
                current = current.next;
            }

            while (current != null && list2Current != null && list2Current.data < current.data) {
                list2Current = list2Current.next;
            }

            if (current != null && list2Current != null && current.data == list2Current.data) {
                // prev can only be null if current is still pointing at the front of list1
                if (prev == null) {
                    ListNode nextup = current.next;
                    current.next = null;
                    current = nextup;
                    head = current;
                } else {
                    prev.next = current.next;
                    current = prev.next;
                }
            } else if (current != null) {
                prev = current;
                current = current.next;
            }
        }
        front = head;
    }
}

Answer 1

There's no faster than O(M+N) solution to this problem as all elements of both list should be iterated over. However, the solution could be coded simpler, for example:

    public void removeAll(LinkedIntList list2) {
        ListNode previous = front;
        ListNode current = front;
        ListNode toRemove = list2.front;

        while (current != null && toRemove != null) {
            if (current.data < toRemove.data) {
                previous = current;
                current = current.next;
            } else if (current.data > toRemove.data) {
                toRemove = toRemove.next;
            } else {
                if (current == front) {
                    front = current.next;
                } else {
                    previous.next = current.next;
                }
                current = current.next;
            }
        }
    }