[剑指 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：穿针引线。

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