题目描述
链表的节点定义如下:
public class ListNode {
int val;
ListNode next = null;
}
剑指 Offer 25. 合并两个排序的链表
难度简单97
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
限制:
0 <= 链表长度 <= 1000
测试用例
- 功能测试(输入的两个链表有多个节点;节点的值互不相同或者存在值相等的多个节点)
- 特殊输入测试(两个节点的一个或者连个节点为空指针;两个链表中只有一个节点)
题目考点
- 考察应聘者分析问题的能力。
- 考察应聘者能不能写出鲁棒的代码。
解题思路
当我们得到两个链表中较小的头节点并把它连接到新链表,两个链表剩余的节点依然是有序的,因此合并的步骤和之前啊的步骤是一样的,这就是典型的递归过程。所以我们只要用递归的方法解决就好了。
自己解题
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dum = new ListNode(0), cur = dum;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
}
else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return dum.next;
}
}