【Offer】[25] 【合并两个排序的链表】
2024-08-26 22:06:17
题目描述
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。例如，输入图中的链表1和链表2,则合并之后的升序链表如链表3所示。链表节点定义如下:

思路分析
- 非递归，设置一个头结点，比较两个链表中的值，通过头结点将其串联起来，最后返回的是头结点的next
- 递归方法。
测试用例
- 功能测试：输入的两个链表有多个节点;节点的值互不相同或者存
在值相等的多个节点 - 特殊输入测试：两个链表的一个或者两个头节点为nullptr 指针;
两个链表中只有一个节点
Java代码
public class Offer25 {
public static void main(String[] args) {
test1();
test2();
test3();
test4();
}
public static ListNode Merge(ListNode l1, ListNode l2) {
return Solution3(l1, l2);
}
private static ListNode Solution1(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head = new ListNode(-1);
ListNode p = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
if (l1 == null) {
p.next = l2;
} else {
p.next = l1;
}
}
return head.next;
}
private static ListNode Solution2(ListNode l1, ListNode l2) {
ListNode pHead = new ListNode(-1);
ListNode p = pHead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 == null) {
p.next = l2;
} else {
p.next = l1;
}
return pHead.next;
}
/**
* 递归的方法
*
* @param l1
* @param l2
* @return
*/
private static ListNode Solution3(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = Solution3(l1.next, l2);
return l1;
} else {
l2.next = Solution3(l1, l2.next);
return l2;
}
}
private static void test1() {
ListNode l1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(5);
ListNode node4 = new ListNode(7);
ListNode node5 = new ListNode(9);
ListNode node6 = new ListNode(11);
l1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
ListNode l2 = new ListNode(4);
ListNode node22 = new ListNode(6);
ListNode node23 = new ListNode(8);
ListNode node24 = new ListNode(13);
l2.next = node22;
node22.next = node23;
node23.next = node24;
System.out.println("链表1：");
ListNode.printListNode(l1);
System.out.println("链表2");
ListNode.printListNode(l2);
ListNode merge = Merge(l1, l2);
System.out.println("合并的链表--->");
ListNode.printListNode(merge);
}
private static void test2() {
ListNode l1 = new ListNode(1);
ListNode node2 = new ListNode(1);
ListNode node3 = new ListNode(1);
ListNode node4 = new ListNode(2);
ListNode node5 = new ListNode(4);
ListNode node6 = new ListNode(5);
l1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
ListNode l2 = new ListNode(1);
ListNode node22 = new ListNode(5);
ListNode node23 = new ListNode(5);
ListNode node24 = new ListNode(8);
l2.next = node22;
node22.next = node23;
node23.next = node24;
System.out.println("链表1：");
ListNode.printListNode(l1);
System.out.println("链表2");
ListNode.printListNode(l2);
ListNode merge = Merge(l1, l2);
System.out.println("合并的链表--->");
ListNode.printListNode(merge);
}
private static void test3() {
ListNode l1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(7);
l1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
System.out.println("链表1：");
ListNode.printListNode(l1);
ListNode l2 = null;
System.out.println("链表2");
ListNode.printListNode(l2);
ListNode merge = Merge(l1, l2);
System.out.println("其中类l2为null,合并的链表--->");
ListNode.printListNode(merge);
}
private static void test4() {
System.out.println("都为null，合并链表--->");
ListNode merge = Merge(null, null);
ListNode.printListNode(merge);
}
}
代码链接
最新文章
- JSP动作元素之useBean、setProperty、getProperty指令
- Xcode8 适配iOS10时遇见的一些问题
- 调用C++动态链接库出现错误
- python中x,y交换值的问题
- 解决asp.net动态压缩
- java常用集合类：Deque，ArrayList，HashMap，HashSet
- 李洪强iOS开发之【零基础学习iOS开发【01-前言】03-前景和难易度分析
- hadoop集群监控工具ambari安装
- 安卓Service完全解析(上)
- c#params应用
- 译-Web Service剖析: XML, SOAP 和WSDL 用于独立于平台的数据交换
- Collect devices information
- 并行排序ShearSort ---[MPI , c++]
- P1122 最大子树和
- 【HANA系列】SAP HANA XS使用Data Services查询CDS实体【一】
- C++ Standards Support in GCC - GCC 对 C++ 标准的支持
- django 定义文章url
- Go Example--Hello
- Linux(CentOS)搭建SVN服务器
- js dictionary字典 遍历