《劍指offer》面試題25：輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

思路一：歸并排序的思想（非遞歸方式）

代碼如下：

public ListNode merge1(ListNode list1,ListNode list2) {
    if (list1 == null) {
        return list2;
    } else if (list2 == null) {
        return list1;
    } else {
        ListNode node1 = list1;
        ListNode node2 = list2;
        // 確定合并后的新鏈表的頭節(jié)點(diǎn)
        ListNode mergeHead = null;
        if (node1.val > node2.val) {
            mergeHead = node2;
            node2 = node2.next;
        } else {
            mergeHead = node1;
            node1 = node1.next;
        }
        // 歸并的過(guò)程
        ListNode curNode = mergeHead;
        while (node1 != null && node2 != null) {
            if (node1.val > node2.val) {
                curNode.next = node2;
                node2 = node2.next;
            } else {
                curNode.next = node1;
                node1 = node1.next;
            }
            curNode = curNode.next;
        }
        // 有一個(gè)鏈表歸并完，另一個(gè)鏈表剩余的節(jié)點(diǎn)接上
        if (node1 == null) {
            curNode.next = node2;
        }
        if (node2 == null) {
            curNode.next = node1;
        }
        return mergeHead;
    }
}

思路二：每次比較兩個(gè)節(jié)點(diǎn)的val的大小實(shí)際是重復(fù)的過(guò)程，可以借助遞歸函數(shù)實(shí)現(xiàn)。

代碼如下：

public ListNode merge2(ListNode list1,ListNode list2) {
    if (list1 == null) {
        return list2;
    } else if (list2 == null) {
        return list1;
    } else {
        ListNode mergeHead = null;
        if (list1.val > list2.val) {
            mergeHead = list2;
            mergeHead.next = merge2(list1,list2.next);
        } else {
            mergeHead = list1;
            mergeHead.next = merge2(list1.next,list2);
        }
        return mergeHead;
    }
}