這是悅樂書的第148次更新操软，第150篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第7題（順位題號(hào)是21）六水。合并兩個(gè)已排序的鏈表并將其作為新鏈表返回脑漫。 新鏈表應(yīng)該通過拼接前兩個(gè)鏈表的節(jié)點(diǎn)來完成秸仙。例如：

鏈表L1包含三個(gè)節(jié)點(diǎn)，為1,2,4
鏈表L2包含三個(gè)節(jié)點(diǎn)胜榔，為1,3,4
將L1和L2合并后的新鏈表包含6個(gè)節(jié)點(diǎn)，為1,1,2,3,4,4

本次解題使用的開發(fā)工具是eclipse湃番，jdk使用的版本是1.8夭织，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測(cè)試吠撮。

02 此題中的鏈表是什么尊惰？

先來看段代碼，下面是定義的ListNode類，有兩個(gè)屬性弄屡，一個(gè)是存儲(chǔ)整數(shù)值的val题禀，一個(gè)是ListNode類本身的next，存儲(chǔ)下一個(gè)ListNode的地址值（指針）膀捷。形象的解釋就是迈嘹，鏈表可以是拉鏈的齒輪，互相咬合全庸；也可以是電影《盜夢(mèng)空間》中的夢(mèng)中夢(mèng)秀仲；就像大盒子里面可以繼續(xù)放盒子一樣。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

為了更好的理解鏈表是怎么存儲(chǔ)值的壶笼，且看下面的代碼神僵。l1的next屬性引用了l2，l2的next屬性引用了l3覆劈。

public class Easy_21_MergeTwoSortedList {

    public static void main(String[] args) {
        Easy_21_MergeTwoSortedList instance = new Easy_21_MergeTwoSortedList();
        ListNode l1 = new ListNode(1);
        ListNode l2 =new ListNode(2);
        ListNode l3 =new ListNode(4);
        l1.next = l2;
        l2.next = l3;   
        System.out.println(instance.listNodeToString(l1));
        ListNode l4 = new ListNode(1);
        ListNode l5 =new ListNode(3);
        ListNode l6 =new ListNode(4);
        l4.next = l5;
        l5.next = l6;
        System.out.println(instance.listNodeToString(l4));
    }
    
    public String listNodeToString(ListNode L){
        List<Integer> list = new ArrayList<Integer>();
        while(L != null){
            list.add(L.val);
            L = L.next;
        }
        return list.toString();
    }
}

03 第一種解法

因?yàn)榻o的鏈表都是已經(jīng)排過序的（由小到大）保礼，只需要依次比較兩個(gè)鏈表的元素val值即可，并且存入一個(gè)新的鏈表里面责语。如果某一個(gè)鏈表先循環(huán)完炮障，新鏈表剩下的元素就是另外一個(gè)鏈表剩下的元素。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1); 
    ListNode cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

04 第二種解法

像第二種方法循環(huán)判斷再取值的情況鹦筹，很容易聯(lián)想到遞歸铝阐，即自己調(diào)用自己，同時(shí)給予退出條件即可铐拐。使用遞歸的好處就是代碼量少徘键。

public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists2(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists2(l1, l2.next);
        return l2;
    }
}

05 小結(jié)

此題雖然不難，但是需要先將題目意思讀懂遍蟋，并且知道鏈表是怎么存數(shù)據(jù)的吹害，這樣才能更好解題。為了更好理解虚青，下面貼上全部代碼它呀。

package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 合并兩個(gè)已排序的鏈接列表并將其作為新列表返回。 新列表應(yīng)該通過拼接前兩個(gè)列表的節(jié)點(diǎn)來完成棒厘。
 * 例：
 * 輸入：1-> 2-> 4, 1-> 3-> 4
 * 輸出：1-> 1-> 2-> 3-> 4-> 4
 * @author 小川94
 * @date 2018-10-21
 */
public class Easy_21_MergeTwoSortedList {

    public static void main(String[] args) {
        Easy_21_MergeTwoSortedList instance = new Easy_21_MergeTwoSortedList();
        ListNode l1 = new ListNode(1);
        ListNode l2 =new ListNode(2);
        ListNode l3 =new ListNode(4);
        l1.next = l2;
        l2.next = l3;   
        System.out.println(instance.listNodeToString(l1));
        ListNode l4 = new ListNode(1);
        ListNode l5 =new ListNode(3);
        ListNode l6 =new ListNode(4);
        l4.next = l5;
        l5.next = l6;
        System.out.println(instance.listNodeToString(l4));
        ListNode result = instance.mergeTwoLists2(l1, l4);
        System.out.println(instance.listNodeToString(result));
    }
    
    public String listNodeToString(ListNode L){
        List<Integer> list = new ArrayList<Integer>();
        while(L != null){
            list.add(L.val);
            L = L.next;
        }
        return list.toString();
    }
    
    /**
     * 順位循環(huán)判斷
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1); 
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    /**
     * 利用遞歸
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }
    }
    
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

此題解法遠(yuǎn)不止上面這兩種纵穿，如果大家有什么好的解法思路、建議或者其他問題奢人，可以下方留言交流谓媒，點(diǎn)贊、留言何乎、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持句惯！