美文网首页
21. 合并两个有序链表

21. 合并两个有序链表

作者: 雇个城管打天下 | 来源:发表于2018-04-29 13:15 被阅读344次

    题目


    在这里给出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;
        }
    }
    

    相关文章

      网友评论

          本文标题:21. 合并两个有序链表

          本文链接:https://www.haomeiwen.com/subject/frvolftx.html