8.1 MERGE TWO SORTED LISTS (avoid modification)

#1

Hello,

I try to avoid modification of original lists passed in - by copying the data from the link node

The original Java solution:

  public static ListNode<Integer> mergeTwoSortedLists(ListNode<Integer> L1,
                                                      ListNode<Integer> L2) {
    // Creates a placeholder for the result.
    ListNode<Integer> dummyHead = new ListNode<>(0, null);
    ListNode<Integer> current = dummyHead;
    ListNode<Integer> p1 = L1, p2 = L2;

    while (p1 != null && p2 != null) {
      if (p1.data <= p2.data) {
        current.next = p1;
        p1 = p1.next;
      } else {
        current.next = p2;
        p2 = p2.next;
      }
      current = current.next;
    }

    // Appends the remaining nodes of p1 or p2.
    current.next = p1 != null ? p1 : p2;
    return dummyHead.next;
  }

My solution to avoid modification:

  public static ListNode<Integer> mergeTwoSortedListsWithoutModifyingOriginal(ListNode<Integer> L1,
                                                      ListNode<Integer> L2) {
    // Creates a placeholder for the result.
    ListNode<Integer> dummyHead = new ListNode<>(0, null);
    ListNode<Integer> current = dummyHead;
    ListNode<Integer> p1 = L1, p2 = L2;

    while (p1 != null && p2 != null) {
      if (p1.data <= p2.data) {
        current.next = new ListNode(p1.data, null);
        p1 = p1.next;
      } else {
        current.next = new ListNode(p2.data, null);
        p2 = p2.next;
      }
      current = current.next;
    }

    // Appends the remaining nodes of p1 or p2.
    current.next = p1 != null ? new ListNode(p1.data, p1.next) : p2 != null ? new ListNode(p2.data, p2.next) : null;
    return dummyHead.next;
  }
0 Likes
#2

Hi,

there is no point in this line:

current.next = p1 != null ? new ListNode(p1.data, p1.next) : p2 != null ? new ListNode(p2.data, p2.next) : null;

because you can connect current and p1/p2 directly without creating a new node.

current.next = p1 != null ? p1 : p2;

0 Likes
#3

Hey ashkar,

In fact, you might misunderstand the problem statement that we are trying to merge the two lists in-place. As you can see in the illustrated example figure, there is gray text under each node which represents its address. After merging, those nodes are still having the same addresses which means we are merging instead of creating new nodes.

0 Likes