每日一道 LeetCode (7)：合并兩個(gè)有序鏈表

?

每天 3 分鐘，走上算法的逆襲之路。

?

前文合集

每日一道 LeetCode 前文合集

代碼倉庫

GitHub：https://github.com/meteor1993/LeetCode

Gitee：https://gitee.com/inwsy/LeetCode

題目：合并兩個(gè)有序鏈表

題目來源：https://leetcode-cn.com/problems/merge-two-sorted-lists/

將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

解題方案：迭代

首先需要了解一下鏈表的數(shù)據(jù)結(jié)構(gòu)，如果這個(gè)不清楚這道題完全沒得玩。

我還是先寫下定義鏈表的代碼，配合代碼好理解一下：

public class ListNode {

    public int val;
    public ListNode next;

    public ListNode() {

    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode (int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

這段代碼異常簡單，定義了一個(gè)數(shù)據(jù)域用來存放一個(gè)整數(shù) val ，然后定義了一個(gè)指針指向另一個(gè) ListNode ，這就形成了一個(gè)單獨(dú)的鏈表上的節(jié)點(diǎn)。

接下來是排序，我相信如果是兩個(gè)數(shù)組排序大多數(shù)人應(yīng)該都寫的出來，實(shí)際上鏈表的排序和數(shù)組的排序也差不多，正向思維就是直接循環(huán)排序，簡單粗暴。

思路簡單代碼也簡單，看下我寫的單純的迭代排序的代碼：

// 暴力迭代
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode prehead = new ListNode(-1);

    ListNode prev = prehead;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }

    prev.next = l1 == null ? l2 : l1;

    return prehead.next;
}

是不是很簡單，判斷兩個(gè)鏈表節(jié)點(diǎn)的大小，然后修改指針的指向，接著循環(huán)，循環(huán)到兩個(gè)節(jié)點(diǎn)都為 null 為止。

需要注意的是當(dāng)循環(huán)終止的時(shí)候， l1 和 l2 最多有一個(gè)是非空的，這時(shí)候需要在

解題思路：遞歸

秉承著良好的習(xí)慣，做完題以后看下答案，大體排序思路沒什么滑頭，但是看到了另一種寫法，這個(gè)寫法寫起來說實(shí)話，還真有點(diǎn)不大會(huì)寫。

雖然這么說有點(diǎn)丟人，但我就是這么不要臉，就這么直接說出來了，遞歸這種方式，平時(shí)基本不怎么寫，突然冷不丁的讓我寫一下，還是蠻困難的。

// 遞歸
public ListNode mergeTwoLists_1(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    else if (l2 == null) return l1;
    else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

遞歸的代碼看起來是十分簡潔的，簡潔的代價(jià)是可讀性降低。

不過話說回來，遞歸的寫法是每一位碼農(nóng)都應(yīng)該熟悉的，雖然不常用。。。

PS：又找到自己短板了，每天能通過這種方式發(fā)現(xiàn)一個(gè)短板補(bǔ)一個(gè)短板還是很開心的。