题目
在这里给出ListNode类
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
解析
本题考的是链表，但是难度不大，因为题目刚开始已经说了，是将两个有序链表合并成一个新的有序链表，已经知道是有序的了，剩下的无非是进行一个再排序的过程。大致思路如下：
- 设第一个ListNode为l1，那么之后的就是l1.next,l1.next.next......
- 设第二个ListNode为l2，那么之后的就是l2.next,l2.next.next......
- 设置第三个ListNode为l0，作为我们最后需要返回的ListNode对象。
- 先比较l1.val和l2.val，如果l1.val<l2.val，那么在新链表中，l1肯定是在l2前，所以此时lo=l1，反之l0=l2.
- 接下来寻找l0.next,如果已经得知l1.val<v2.val，那么 就需要l1.next和l2进行比较；反之如果l1.val>v2.val,那么就需要l1和l2.next进行比较了
- 如此递归下去知道最后没有了，递归结束
代码
public class Main {
public static void main(String[] args) {
ListNode l1 = new ListNode(0);
l1.next = new ListNode(2);
l1.next.next = new ListNode(5);
l1.next.next.next = new ListNode(7);
ListNode l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(5);
ListNode l = new Main().mergeTwoLists(l1, l2);
while (l != null) {
System.out.print(l.val+" ");
l = l.next;
}
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode l0 = null;
if (l1.val<l2.val){
l0=l1;
l0.next=mergeTwoLists(l1.next,l2);
}else {
l0=l2;
l0.next=mergeTwoLists(l1,l2.next);
}
return l0;
}
}
