21. 合并两个有序链表

题目

在这里给出ListNode类

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

解析

本题考的是链表，但是难度不大，因为题目刚开始已经说了，是将两个有序链表合并成一个新的有序链表，已经知道是有序的了，剩下的无非是进行一个再排序的过程。大致思路如下：

1. 设第一个ListNode为l1，那么之后的就是l1.next,l1.next.next......
2. 设第二个ListNode为l2，那么之后的就是l2.next,l2.next.next......
3. 设置第三个ListNode为l0，作为我们最后需要返回的ListNode对象。
4. 先比较l1.val和l2.val，如果l1.val<l2.val，那么在新链表中，l1肯定是在l2前，所以此时lo=l1，反之l0=l2.
5. 接下来寻找l0.next,如果已经得知l1.val<v2.val，那么 就需要l1.next和l2进行比较；反之如果l1.val>v2.val,那么就需要l1和l2.next进行比较了
6. 如此递归下去知道最后没有了，递归结束

代码

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;
    }
}