简单
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:使用虚拟节点比较两个链表的结点,哪个值小,就把哪个节点插在虚拟节点后边
- 首先,我们设定一个哨兵节点 newHead ,这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 temp 指针,我们需要做的是调整它的 next 指针。
- 然后,我们重复以下过程,直到headA 或者headB 指向了 null :如果headA 当前节点的值小于等于headB ,我们就把 headA 当前的节点接在temp节点的后面同时将 headA 指针往后移一位。否则,我们对headB做同样的操作。不管我们将哪一个元素接在了后面,我们都需要把 temp向后移一位。
- 在循环终止的时候,headA 和 headB 至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并链表即可。
public static ListNode mergeTwoLists(ListNode headA, ListNode headB) {
//虚拟节点
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while (headA != null && headB != null){
if (headA.val < headB.val){
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if (headA != null){
tmp.next = headA;
}
if (headB != null){
tmp.next = headB;
}
return newHead.next;
}