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

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 <