# 剑指 Offer 25. 合并两个排序的链表

示例1：

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

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # 关键条件递增
        # 通过指针对比反复对比链接
        dummy_head = ListNode(0)
        cur = dummy_head
        cur1, cur2 = l1, l2

        while cur1 and cur2:
            if cur1.val >= cur2.val:
                cur.next = cur2
                cur2 = cur2.next
            else:
                cur.next = cur1
                cur1 = cur1.next
            cur = cur.next # 前面操作只是找到cur的next，还需要cur进行移动
        cur.next = cur1 if cur1 else cur2 #连接剩下的链表
        return dummy_head.next