牛客网地址：https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=295&tqId=23267&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

链表BM4：

题目如下：

Python实现代码如下：

#
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
#

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # 初始化合并链表的节点head
        head = ListNode(0)
        # 另外定义一个链表节点，指向head；因为head会随着合并链表节点的增加而变化
        return_head = head

        # pHead1和pHead2都有节点时，循环比较节点的val值
        while pHead1 and pHead2:
            # 取val值较小的节点，使合并链表的head的下一个节点指向该节点，即head.next = pHeadx；
            # pHead1或pHead2取出一个节点到合并链表后，后移一个节点，即pHeadx = pHeadx.next
            if pHead1.val <= pHead2.val:
                head.next = pHead1
                pHead1 = pHead1.next
            else:
                head.next = pHead2
                pHead2 = pHead2.next
            # 合并链表的指针指向下一个节点位置
            head = head.next

        # 哪个链表还有节点，则直接接在合并链表之后
        if pHead1:
            head.next = pHead1
        if pHead2:
            head.next = pHead2

        # 返回另外定义的不变的链表节点的下一个节点位置，去掉初始化的ListNode(0)
        return return_head.next


node1, node2 = ListNode(-1), ListNode(10)
node1.next = node2
node3, node4, node5 = ListNode(1), ListNode(8), ListNode(12)
node3.next = node4
node4.next = node5

s = Solution()
a = s.Merge(node1, node3)
print(a.val, a.next.val, a.next.next.val, a.next.next.next.val, a.next.next.next.next.val)

解题思路：

        与合并两个有序数组类似，依次比较数组中的两个数值，小的先放到合并数组内，同时指针右移，直到其中一个数组比完；再将剩余数组中的值都加入到合并数组内。合并两个有序链表思路相同，具体代码和详细注释如上，可供参考。

        需注意，链表中的节点是ListNode类型的，如果需要举例验证解法是否正确，需要先初始化ListNode类型的节点，再将节点链接起来成为链表，取链表的头结点代入参数（示例如上代码所示）。