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

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围： 0≤n≤1000，−1000≤节点值≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n)

#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        node1 = pHead1
        node2 = pHead2
        result = pHead1
        if node1.val > node2.val:
            result = pHead2
            node2 = node2.next
        else :
            node1 = node1.next
        current_node = result
        while ((node1 != None) and (node2 != None)):
            if (node1.val <= node2.val):
                current_node.next = node1
                node1 = node1.next
            else:
                current_node.next = node2
                node2 = node2.next
            current_node = current_node.next
        if node2 != None:
            current_node.next = node2
        elif node1 != None:
            current_node.next = node1
        return result

题目不难，解法也不难，就比较两个链表的第一个元素的值，小的元素就接到结果链表后面，同时该元素指针后移，一直到结尾就可以了