[数据结构与算法]数据结构：1.合并两个有序链表

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

?迭代方法思路：从两个链表的头结点开始对应比较：当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，对应链表中的节点向后移一位。直到一个链表到了尾结点，将另一个非空的链表直接添加到尾部。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *prehead = new ListNode(0);//新建哑节点，值为-1
        ListNode *prev = prehead; 
        //在对链表的操作中，链表的头节点prev往往会发生移动，这样我们将难以找到最终链表的头指针，故我们需要提前设置一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回最终的链表。
        while (l1 != nullptr && l2 != nullptr) {//当有一个链表到达尾节点，结束循环
            if (l1->val <= l2->val) {//l1当前节点小于等于l2当前节点，接入l1当前节点，否则接入l2当前节点
                prev->next = l1;
                l1 = l1->next; //l1指针后移
            } else {            
                prev->next = l2; 
                l2 = l2->next; //l2指针后移
            }
            prev = prev->next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = l1 == nullptr ? l2 : l1;

        return prehead->next;
    }

};

时间复杂度：O（m+n）

空间复杂度：O（1）