[Leetcode] 21. Merge Two Sorted Lists

題目

Merge two sorted linked lists and return it as a new list.
The new list should be made by splicing together the nodes of the first two lists.

看完題目, 以為可以用 LinkedList 這類的東西, 想說 ez ...
結果下面給的 hint Sample 根本就不是那麼一回事啊, 抓頭抓抓抓...

/**
 * Definition for singly-linked list.
 *
 */
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

先拿到測試資料

/**
 * Created by jerry on 2017/9/24.
 *
 * Merge two sorted linked lists and return it as a new list.
 * The new list should be made by splicing together the nodes of the first two lists.
 */
public class LeetCode21MergeTwoSortedListsTest {

    private LeetCode21MergeTwoSortedLists sol = new LeetCode21MergeTwoSortedLists();

    @Test
    public void test1() {
        final ListNode l1 = null;
        final ListNode l2 = new ListNode(0);

        ListNode act = sol.mergeTwoLists(l1, l2);

        Assert.assertEquals(0, act.val);
    }

    @Test
    public void test2() {
        final ListNode l1 = new ListNode(2);
        final ListNode l2 = new ListNode(1);

        ListNode act = sol.mergeTwoLists(l1, l2);

        Assert.assertEquals(1, act.val);
        Assert.assertEquals(2, act.next.val);
    }

    @Test
    public void test3() {
        final ListNode l1 = new ListNode(1);
        final ListNode l2 = new ListNode(2);

        ListNode act = sol.mergeTwoLists(l1, l2);

        Assert.assertEquals(1, act.val);
        Assert.assertEquals(2, act.next.val);
    }

    @Test
    public void test4() {
        final ListNode l1 = new ListNode(5);
        final ListNode l2 = new ListNode(1);
        final ListNode l3 = new ListNode(2);
        final ListNode l4 = new ListNode(4);
        l2.next = l3;
        l3.next = l4;

        ListNode act = sol.mergeTwoLists(l1, l2);
        Assert.assertEquals(1, act.val);
        Assert.assertEquals(2, act.next.val);
        Assert.assertEquals(4, act.next.next.val);
        Assert.assertEquals(5, act.next.next.next.val);
    }

    @Test
    public void test5() {
        final ListNode l1 = new ListNode(-9);
        final ListNode l2 = new ListNode(3);
        l1.next = l2;

        final ListNode l3 = new ListNode(5);
        final ListNode l4 = new ListNode(7);
        l3.next = l4;

        ListNode act = sol.mergeTwoLists(l1, l3);

        Assert.assertEquals(-9, act.val);
        Assert.assertEquals(3, act.next.val);
        Assert.assertEquals(5, act.next.next.val);
        Assert.assertEquals(7, act.next.next.next.val);
    }
}

Solution

還是抓不太到這種遞迴的解法, 有種輾轉互相比較的意味

public class LeetCode21MergeTwoSortedLists {
    // [-9, 3], [5, 7]
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (Objects.isNull(l1)) return l2;
        if (Objects.isNull(l2)) return l1;

        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l2, l1.next);
            return l1;

        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}