25、合并两个有序链表（递归没看）

回顾：[3.24]

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

方法1、迭代法

回顾思路：

1、设立一个dummy节点，指向-1，pre指向dummy。idx1，idx2指向两个链表；
2、判断idx1和idx2的大小，小的赋值给pre.next，接着pre、小的idx都后移，循环遍历。
3、直到有一个idx为空，把另外一个idx剩下的赋值给pre。

执行用时：28 ms, 在所有 Python3 提交中击败了98.69%的用户

内存消耗：15 MB, 在所有 Python3 提交中击败了34.82%的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        pre = dummy
        idx1, idx2 = list1, list2
        while idx1 and idx2:
            if idx1.val <= idx2.val:
                pre.next = idx1
                idx1 = idx1.next
            else:
                pre.next = idx2
                idx2 = idx2.next
            pre = pre.next
        # pre.next = idx1 if idx2 is None else idx2
        if idx1 is None:
            pre.next = idx2
        if idx2 is None:
            pre.next = idx1
        return dummy.next