题目描述:输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
设置一个“哨兵节点”叫 preHead,这会让代码写起来非常“清爽”。整体流程如下:
时间复杂度是 O(N),空间复杂度是 O(1)。代码如下:
// ac地址:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
// 原文地址:https://xxoo521.com/2020-01-12-merge-two-sorted-lists/
/**
* @param {ListNode} pHead1
* @param {ListNode} pHead2
* @return {ListNode}
*/
var mergeTwoLists = function(pHead1, pHead2) {
if (!pHead1) {
return pHead2;
} else if (!pHead2) {
return pHead1;
}
let preHead = new ListNode(-1);
let node = preHead;
while (pHead1 && pHead2) {
if (pHead1.val <= pHead2.val) {
node.next = pHead1;
pHead1 = pHead1.next;
} else {
node.next = pHead2;
pHead2 = pHead2.next;
}
node = node.next;
}
if (pHead1) {
node.next = pHead1;
} else if (pHead2) {
node.next = pHead2;
}
return preHead.next;
};