题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路1：

分别用p1,p2两个指针扫描两个有序链表，p3指针去构建新链表h3.

p1.val <= p2.val，则p3把p1指向的结点加入h3,p1后移动。反之，对p2进行对应操作。

代码：(未验证正确性，提交时显示超时，所以不知道功能是否实现，还是仅仅时间复杂度高？)

public ListNode Merge(ListNode list1,ListNode list2) {

        if(list1 == null){

            return list2;

        }

        if(list2 == null){

            return list1;

        }

        ListNode p1 = list1;

        ListNode p2 = list2;

        ListNode list3;

        if(list1.val <= list2.val){

            list3 = list1;

        }else{

            list3 = list2;

        }

        ListNode p3 = list3;

        while(p1 != null && p2 != null){

            if(p1.val <= p2.val){

                p3.next = p1;

                p1 = p1.next;

            }else{

                p3.next = p2;

                p2 = p2.next;

            }

            p3 = p3.next;

        }

        if(p1 == null){

            p3.next = p2;

        }

         if(p2 == null){

            p3.next = p1;

        }

        return list3;

    }

思路2：

采用递归的思想

代码：

public ListNode Merge(ListNode list1,ListNode list2) {

        if(list1 == null){

            return list2;

        }

        if(list2 == null){

            return list1;

        }

        ListNode list3;

        if(list1.val <= list2.val){

            list3 = list1;

            list3.next = Merge(list1.next, list2);

        }else{

            list3 = list2;

            list3.next = Merge(list1, list2.next);

        }

        return list3;

    }