《剑指 Offer （第 2 版）》第 25 题：合并两个排序的链表

第 25 题：合并排序的链表

传送门：AcWing：合并两个排序的链表，牛客网 online judge 地址。

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

样例：

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

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

分析：同 LeetCode 第 21 题，传送门：21. 合并两个有序链表。这是一道经典的问题，可以使用“穿针引线”，也可以使用递归求解，个人觉得递归的代码比较简洁易懂。“穿针引线”则要画图。

思路1： 使用递归，编码简单。

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

        # 代码能走到这里说明 l1 和 l2 均非空
        # 比较哪个小就行了
        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 题：合并两个排序的链表-1

《剑指 Offer （第 2 版）》第 25 题：合并两个排序的链表-2

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
        """
        # 引入头结点可以简化对问题的讨论
        dummy_node = ListNode(-1)
        cur_node = dummy_node
        p1 = l1
        p2 = l2

        while p1 and p2:
            # 两者都不为空，才须要比较
            # 其中有一个为空的时候，把其中一个接到另一个尾巴就好了
            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
        # 跳出循环的时候，一定有：p1 为空或者 p2 为空
        # 其中有一个为空的时候，把其中一个接到另一个尾巴就好了
        if p1 is None:  # 这一句写成 if not p1 也是可以的，不过不好理解
            cur_node.next = p2
        if not p2:
            cur_node.next = p1
        return dummy_node.next