数据结构与算法：合并链表、链表分割及回文结构

1. 合并链表

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

示例：

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

输入： l1 = [], l2 = []
输出： []

输入： l1 = [], l2 = [0]
输出： [0]

分析：这道题使用迭代法实现最为直观，即每次比较两个链表当前节点的大小，调整节点间的顺序。具体思想如下所示：

虽然也可以重新建立一个新的链表进行尾插，但这会使空间复杂度变为 O(n)。尽管本题未做强制要求，但尽量优化空间复杂度。

最正常的比较过程代码如下：

while (list1 && list2) {
    if (list1->val < list2->val) {
        cur->next = list1;
        list1 = list1->next;
    } else {
        cur->next = list2;
        list2 = list2->next;
    }
    cur = cur->next;
}

若其中一个链表为空，则将另一个链表的剩余部分直接接在结果链表后即可。