8.1. Merge two sorted lists

**ericntd** · June 1, 2020, 8:02pm

I believe that the solution in the book (2015 edition) is incomplete:
Solution in the book

gist.github.com

https://gist.github.com/ericntd/ccc0c249de277f514fbcaf5346cc60f5

book-solution-merge-two-sorted-lists.java

public static final ListNode<Integer> mergeTwoSortedLists(ListNode<Integer> L1, ListNode<Integer> L2) {
        System.out.printf(">>> Merging %s and %s", L1, L2);
        System.out.println();
        ListNode<Integer> dummyHead = new ListNode<>(new Random().nextInt(), (ListNode<Integer>) null);
        ListNode<Integer> current = dummyHead;
        ListNode<Integer> p1 = L1;

        ListNode<Integer> p2 = L2;
        while (p1.getNext() != null && p2.getNext() != null) {
            if (p1.getData() <= p2.getData()) {

This file has been truncated. show original

This yields “2 -> 3 -> 5 -> 7 -> null” for L1 = “2 -> 5 -> 7 -> null” and L2 = “3 -> 11 -> null” which is wrong
More test results:

Merging 1 -> 3 -> 5 -> null and 2 -> 4 -> 6 -> null
<<< Merge result : 1 -> 2 -> 3 -> 5 -> null

Merging 1 -> 3 -> null and 2 -> 4 -> 6 -> null
<<< Merge result : 1 -> 3 -> null

Merging 1 -> null and 2 -> 4 -> 6 -> null
<<< Merge result : 1 -> null

Merging 3 -> null and 2 -> 4 -> 6 -> null
<<< Merge result : 3 -> null

Merging 7 -> null and 2 -> 4 -> 6 -> null
<<< Merge result : 7 -> null

I’ve added what I think is necessary and got the tests to pass, in Kotlin, wdyt?

gist.github.com

https://gist.github.com/ericntd/b2201fdf50b62f181c6538841ae6c67d

merge-two-sorted-lists.kt

fun mergeTwoSortedLists(L1: ListNode<Int>, L2: ListNode<Int>): ListNode<Int> {
    println("merging $L1 and $L2")
    val dummyHead = ListNode(Random.nextInt(), null)
    var current = dummyHead
    var p1 = L1
    var p2 = L2
    while (p1.next != null && p2.next != null) {
        if (p1.data <= p2.data) {
            current.next = p1
            p1 = p1.next!!

This file has been truncated. show original