第 25 題：合并排序的鏈表

傳送門：AcWing：合并兩個(gè)排序的鏈表，?？途W(wǎng) online judge 地址。

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

樣例：

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

輸出：1->2->3->4->5->5

分析：同 LeetCode 第 21 題，傳送門：21. 合并兩個(gè)有序鏈表。這是一道經(jīng)典的問(wèn)題，可以使用“穿針引線”，也可以使用遞歸求解，個(gè)人覺(jué)得遞歸的代碼比較簡(jiǎn)潔易懂?！按┽樢€”則要畫圖。

思路1： 使用遞歸，編碼簡(jiǎn)單。

Python 代碼：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
    def merge(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """

        if l1 is None:
            return l2
        if l2 is None:
            return l1

        # 代碼能走到這里說(shuō)明 l1 和 l2 均非空
        # 比較哪個(gè)小就行了
        if l1.val < l2.val:
            l1.next = self.merge(l1.next, l2)
            return l1
        # 走到這里 l1.val >= l2.val
        l2.next = self.merge(l1, l2.next)
        return l2

Java 代碼：

class ListNode {
    int val;
    ListNode next = null;

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

public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}

思路2：穿針引線。

《劍指 Offer （第 2 版）》第 25 題：合并兩個(gè)排序的鏈表-1

《劍指 Offer （第 2 版）》第 25 題：合并兩個(gè)排序的鏈表-2

Python 代碼：

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


# 穿針引線的寫法，一定要畫圖才能寫出來(lái)
# 比較麻煩，還是遞歸處理簡(jiǎn)單

class Solution(object):
    def merge(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # 引入頭結(jié)點(diǎn)可以簡(jiǎn)化對(duì)問(wèn)題的討論
        dummy_node = ListNode(-1)
        cur_node = dummy_node
        p1 = l1
        p2 = l2

        while p1 and p2:
            # 兩者都不為空，才須要比較
            # 其中有一個(gè)為空的時(shí)候，把其中一個(gè)接到另一個(gè)尾巴就好了
            if p1.val < p2.val:
                # next 指針修改
                cur_node.next = p1
                # p1 后移
                p1 = p1.next
            else:
                cur_node.next = p2
                p2 = p2.next
            cur_node = cur_node.next
        # 跳出循環(huán)的時(shí)候，一定有：p1 為空或者 p2 為空
        # 其中有一個(gè)為空的時(shí)候，把其中一個(gè)接到另一個(gè)尾巴就好了
        if p1 is None:  # 這一句寫成 if not p1 也是可以的，不過(guò)不好理解
            cur_node.next = p2
        if not p2:
            cur_node.next = p1
        return dummy_node.next