合併两个有序链表
题目
将两个有序鍊表合併为一个新的有序鍊表并返回。新鍊表是通过拼接给定的两个鍊表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
合併排序
这题等价于合併排序的一部份-合併两个有序的序列，合併后的结果依旧有序。
步骤：
- 比较两个序列的头元素，取其中较小的元素放入新序列
- 被选用的序列把头指针向后移一位
- 重复1和2，直至两个序列都空
举个例子，给定两个有序序列a和b：
比较两个序列的头元素，取较小的（相等的情况下任选其中）。被选取的序列头指针向后移一位。
继续比较两个序列头元素，取较小的。这𥚃b的头元素更小，所以取其加入新序列。
继续比较两个序列头元素，取较小的。这时a的头元素更小，所以取其加入新序列。
继续比较两个序列头元素，取较小的。这时b的头元素更小，所以居其加入新序列。
继续比较两个序列头元素，取较小的。这时两个头元素相等，任选其一。
继续比较两个序列头元素。此时，a序列已空。所以直接从b序列中取元素放入新序列。
至此，两个序列已空，合併完成。
代码
package io.github.rscai.leetcode.bytedance.linktree;
public class Solution1048A {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode la = l1;
ListNode lb = l2;
ListNode head = null;
ListNode currentNode = head;
while (la != null || lb != null) {
if (la == null) {
ListNode newNode = new ListNode(lb.val);
lb = lb.next;
currentNode = addTo(currentNode, newNode);
} else if (lb == null) {
ListNode newNode = new ListNode(la.val);
la = la.next;
currentNode = addTo(currentNode, newNode);
} else if (la.val < lb.val) {
ListNode newNode = new ListNode(la.val);
la = la.next;
currentNode = addTo(currentNode, newNode);
} else {
ListNode newNode = new ListNode(lb.val);
lb = lb.next;
currentNode = addTo(currentNode, newNode);
}
if (head == null) {
head = currentNode;
}
}
return head;
}
private ListNode addTo(ListNode currentNode, ListNode newNode) {
if (currentNode == null) {
return newNode;
}
currentNode.next = newNode;
return newNode;
}
}
复杂度分析
时间复杂度
本演算法对两个序列都只作了一次遍历，所以时间中日人水杂度是：
空间复杂度
使用两个变量head和currentNode。