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

?

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

?

前文合集

每日一道 LeetCode 前文合集

代碼倉庫

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

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

題目：合并兩個有序鏈表

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

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

示例：

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

解題方案：迭代

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

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

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;
    }
}

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

接下來是排序，我相信如果是兩個數(shù)組排序大多數(shù)人應(yīng)該都寫的出來，實際上鏈表的排序和數(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;
}

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

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

解題思路：遞歸

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

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

// 遞歸
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;
    }
}

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

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

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