将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入: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.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
package cn.fansunion.leecode.linkedlist;
/**
* 21. 合并两个有序链表 <br/>将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
* 力扣
*
* @author [email protected]
*
* 2022-2-18
*/
public class MergeTwoSortedLists {
/* 输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
*/
// l1 和 l2 均按 非递减顺序 排列
/**
* 同MergeSortedArray的思路一样,代码结构基本一样。由于链表和数组的特点不同,语法方法上有所差异,核心不同点:4行代码。
*
* @param list1
* @param list2
* @return
*/
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 虚拟1个头结点,方便操作
ListNode head = new ListNode();
ListNode cur = head;
while (list1 != null && list2 != null) {
int val1 = list1.val;
int val2 = list2.val;
if (val1 <= val2) {
// 记录当前节点的下一个节点
ListNode next1 = list1.next;
// 全局当前节点
cur.next = list1;
// 遍历下一个节点
list1 = next1;
cur = cur.next;
} else {
// 记录当前节点的下一个节点
ListNode next2 = list2.next;
// 全局当前节点
cur.next = list2;
// 遍历下一个节点
list2 = next2;
cur = cur.next;
}
}
//todo:可以优化 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
// list1有剩余的
while (list1 != null) {
//务必先临时记录下一个节点,有点“swap交换的味道”
ListNode next1 = list1.next;
cur.next = list1;
list1 = next1;
cur = cur.next;
}
// list2有剩余的
while (list2 != null) {
ListNode next2 = list2.next;
cur.next = list2;
list2 = next2;
cur = cur.next;
}
return head.next;
}
}
package test.leecode.linkedlist;标签:ListNode,cur,3622,list1,list2,链表,有序,new From: https://blog.51cto.com/fansunion/6056786
import org.junit.Assert;
import org.junit.Test;
import cn.fansunion.leecode.linkedlist.ListNode;
import cn.fansunion.leecode.linkedlist.MergeTwoSortedLists;
/**
* @author [email protected]
*
* 2022-2-23
*/
public class MergeTwoSortedListsTest {
// 1245+137=1123457
@Test
public void test1245Plus137() {
MergeTwoSortedLists test = new MergeTwoSortedLists();
ListNode node5 = new ListNode(5, null);
ListNode node4 = new ListNode(4, node5);
ListNode node2 = new ListNode(2, node4);
ListNode list1 = new ListNode(1, node2);
ListNode node7 = new ListNode(7, null);
ListNode node3 = new ListNode(3, node7);
ListNode list2 = new ListNode(1, node3);
ListNode merge1 = test.mergeTwoLists(list1, list2);
int[] merge1Val = merge1.curNextValArray();
Assert.assertArrayEquals(new int[] {1, 1, 2, 3, 4, 5, 7}, merge1Val);
}
// 124+137=112347
@Test
public void test124Plus137() {
MergeTwoSortedLists test = new MergeTwoSortedLists();
ListNode node4 = new ListNode(4, null);
ListNode node2 = new ListNode(2, node4);
ListNode list1 = new ListNode(1, node2);
ListNode node7 = new ListNode(7, null);
ListNode node3 = new ListNode(3, node7);
ListNode list2 = new ListNode(1, node3);
ListNode merge1 = test.mergeTwoLists(list1, list2);
int[] merge1Val = merge1.curNextValArray();
Assert.assertArrayEquals(new int[] {1, 1, 2, 3, 4, 7}, merge1Val);
}
// 124+1378=1123478
@Test
public void test124Plus1378() {
MergeTwoSortedLists test = new MergeTwoSortedLists();
ListNode node4 = new ListNode(4, null);
ListNode node2 = new ListNode(2, node4);
ListNode list1 = new ListNode(1, node2);
ListNode node8 = new ListNode(8, null);
ListNode node7 = new ListNode(7, node8);
ListNode node3 = new ListNode(3, node7);
ListNode list2 = new ListNode(1, node3);
ListNode merge1 = test.mergeTwoLists(list1, list2);
int[] merge1Val = merge1.curNextValArray();
Assert.assertArrayEquals(new int[] {1, 1, 2, 3, 4, 7, 8}, merge1Val);
}
}