合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
codeType
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
codeType
输入：l1 = [], l2 = []
输出：[]
示例 3：
codeType
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按 非递减顺序 排列
解法：
本解法用的是O(1)的空间复杂度的解法，直接串联了原来的两条链表。
ts
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
// 双指针遍历两个链表进行合并即可
if(list1 === null) return list2
if(list2 === null) return list1
let l3 = list1.val > list2.val ? list2 : list1 // 处理起点,先把小的给l3
let p1 = list1.val > list2.val ? list1 : list1.next
let p2 = list1.val > list2.val ? list2.next : list2
let p3 = l3
while(p1 !== null && p2 !== null){
if(p1.val < p2.val){
p3.next = p1
p3 = p3.next
p1 = p1.next
}else{
p3.next = p2
p3 = p3.next
p2 = p2.next
}
}
while(p1 !== null){
p3.next = p1
p3 = p3.next
p1 = p1.next
}
while(p2 !== null){
p3.next = p2
p3 = p3.next
p2 = p2.next
}
return l3
};