题解 | #合并两个排序的链表#

# coding:utf-8
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
# 总体思路：新增一个链表，只需要逐步指向下一个合理的值；pre指针代表虚拟链表的当前节点，pre每次指向下一个值较小的节点，被指向的链表移动到下一个位置（比如这次我选择p1的值，然后p1应该往后移动；同理我选择p2的值应该移动p2）
class Solution:
    def Merge(self, pHead1, pHead2):
        # 逐个遍历，某一个节点，然后对比另外一个链表，比较大小后插入？
        # 不如连接两个链表，再将链表进行排序，但是不满足时间复杂度，需要o(n)
        if pHead2 == None:
            return pHead1
        if pHead1 == None:
            return pHead2
        # 不要陷入排序的思维，已经排序好了，只需要去逐步对比即可
        # 需要一个新的虚拟头节点，这个节点逐步指向合理的下一个节点并且移动这个节点
        P = ListNode(-1)
        pre = P
        p1 = pHead1
        p2 = pHead2
        while (
            p1 and p2
        ):  # 当某一个节点下一个是空的时候代表已经遍历完成了一个节点，不需要继续
            if p1.val <= p2.val:
                # 虚拟节点指向小的那个，并且移动小的那个节点
                # print("p1的值：%s" % (p1.val))
                pre.next = p1
                p1 = p1.next
            else:
                # print("p2的值：%s" % (p2.val))
                pre.next = p2
                p2 = p2.next

            pre = pre.next
        if p1 == None:
            # p1移动完成了，p2还剩余一个
            pre.next = p2
        if p2 == None:
            pre.next = p1
        return P.next