剑指Offer面试题：19.合并两个排序的链表

一、题目
————————————————
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
————————————————
二、思路
————————————————
递归实现：合并过程中，每次都是从两个链表中找出较小的一个来链接，因此可以采用递归来实现：当任意一个链表为null时，直接链接另一个链表即可；其余情况只需要在两个链表中找出较小的一个结点进行链接，该结点的next值继续通过递归函数来链接。
　　非递归实现：非递归实现比较容易想到，直接进行分情况讨论即可，要稍微注意下后面代码中头结点的赋值过程。
————————————————
三、解决问题
————————————————
测试算例　

　　1.功能测试（两个链表有多个或一个结点；结点值相同、不同）

　　2.特殊测试（任意一个或者两个链表的头结点为null）
————————————————

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020-03-24 10:29
 */

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

public class Solution19 {
    public static void main(String[] args) {
        Solution19 demo = new Solution19();
        System.out.println("==============================");
        System.out.println("递归test1");
        demo.test1();
        System.out.println("==============================");
        System.out.println("递归test2");
        demo.test2();
        System.out.println("==============================");
        System.out.println("递归test3");
        demo.test3();
        System.out.println("==============================");
        System.out.println("非递归test4");
        demo.test4();
        System.out.println("==============================");
        System.out.println("非递归test5");
        demo.test5();
        System.out.println("==============================");
        System.out.println("非递归test6");
        demo.test6();
        System.out.println("==============================");
    }
    /*
     * 递归版本
     * 递归实现：
     * 合并过程中，每次都是从两个链表中找出较小的一个来链接，因此可以采用递归来实现：
     * 当任意一个链表为null时，直接链接另一个链表即可；
     * 其余情况只需要在两个链表中找出较小的一个结点进行链接，该结点的next值继续通过递归函数来链接。
     */
    public ListNode Merge01(ListNode list1,ListNode list2) {
        //当任意一个链表为null时，直接链接另一个链表即可；
        if(null == list1){
            return list2;
        }
        if(null == list2){
            return list1;
        }
        //其余情况只需要在两个链表中找出较小的一个结点进行链接，该结点的next值继续通过递归函数来链接。
        if(list1.val < list2.val){
            list1.next = Merge01(list1.next,list2);//
            return list1;
        }else{
            list2.next = Merge01(list1, list2.next);
            return list2;
        }
    }
    /*
     * 非递归版本
     * 非递归实现：非递归实现比较容易想到，直接进行分情况讨论即可，
     * 要稍微注意下后面代码中头结点的赋值过程。
     */
    public ListNode Merge02(ListNode list1,ListNode list2) {
        //当任意一个链表为null时，直接链接另一个链表即可；
        if(null == list1){
            return list2;
        }
        if(null == list2){
            return list1;
        }
        ListNode dummyHead = new ListNode(0);//不能为null
        ListNode temp = dummyHead;
        while(list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        if(null == list1){
            temp.next = list2;
        }else{
            temp.next = list1;
        }
        return dummyHead.next;
    }

    //=====================测试代码=======================
    /*
     * 1.功能测试（两个链表的头结点为null）
     */
    void test1() {
        //1个递增排序的链表
        ListNode list1 = null;
        //1个递增排序的链表
        ListNode list2 = null;

        ListNode head = Merge01(list1, list2);
        if (null == head){
            System.out.println("链表为null");
        }else{
            while(head != null){
                System.out.print(head.val + " ");
                head = head.next;
            }
        }
    }
    /*
     * 2.两个链表有多个结点
     */
    void test2() {
        ListNode list1 = new ListNode(1);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(5);

        ListNode list2 = new ListNode(2);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(6);
        //1个递增排序的链表
        list1.next = node1;
        node1.next = node2;
        //1个递增排序的链表
        list2.next = node3;
        node3.next = node4;

        ListNode head = Merge01(list1,list2);
        if (null == head){
            System.out.println("");
        }else{
            while(head != null){
                System.out.print(head.val + " ");
                head = head.next;
            }
        }
        System.out.println();
    }
    /*
     * 3.两个链表中一个为null,另一个有多个结点
     */
    void test3() {
        ListNode list1 = new ListNode(1);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(5);

        ListNode list2 = null;
        //1个递增排序的链表
        list1.next = node1;
        node1.next = node2;

        ListNode head = Merge01(list1,list2);
        if (null == head){
            System.out.println("");
        }else{
            while(head != null){
                System.out.print(head.val + " ");
                head = head.next;
            }
        }
        System.out.println();
    }
    //=====================测试代码=======================
    /*
     * 1.功能测试（两个链表的头结点为null）
     */
    void test4() {
        //1个递增排序的链表
        ListNode list1 = null;
        //1个递增排序的链表
        ListNode list2 = null;

        ListNode head = Merge02(list1, list2);
        if (null == head){
            System.out.println("链表为null");
        }else{
            while(head != null){
                System.out.print(head.val + " ");
                head = head.next;
            }
        }
    }
    /*
     * 2.两个链表有多个结点
     */
    void test5() {
        ListNode list1 = new ListNode(1);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(5);

        ListNode list2 = new ListNode(2);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(6);
        //1个递增排序的链表
        list1.next = node1;
        node1.next = node2;
        //1个递增排序的链表
        list2.next = node3;
        node3.next = node4;

        ListNode head = Merge02(list1,list2);
        if (null == head){
            System.out.println("");
        }else{
            while(head != null){
                System.out.print(head.val + " ");
                head = head.next;
            }
        }
        System.out.println();
    }
    /*
     * 3.两个链表中一个为null,另一个有多个结点
     */
    void test6() {
        ListNode list1 = new ListNode(1);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(5);

        ListNode list2 = null;
        //1个递增排序的链表
        list1.next = node1;
        node1.next = node2;

        ListNode head = Merge02(list1,list2);
        if (null == head){
            System.out.println("");
        }else{
            while(head != null){
                System.out.print(head.val + " ");
                head = head.next;
            }
        }
        System.out.println();
    }
}

————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。