每天一道算法题——合并两个排序的链表

题目描述

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

测试用例:

{1,3,5},{2,4,6}

对应输出应该为:

{1,2,3,4,5,6}

分析：

1. >第一种方法采用新建一个链表nListNode来存储合并排序后的表。在创建完之后将这个表的头结点存储下来，此处命名为head。并在合并操作完成后返回头结点即可（即return head.next；）
           

class ListNode {//链表的类定义
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Test1 {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1==null) {
            return list2;
        } else if (list2==null) {
            return list1;
        }
        ListNode nListNode = new ListNode();
        nListNode.next = null;
        ListNode head = nListNode;
        while(list1!=null&&list2!=null){
            if (list1.val<list2.val) {
                nListNode.next = list1;
                nListNode = list1;
                list1 = list1.next;
            }else {
                nListNode.next = list2;
                nListNode = list2;
                list2 = list2.next;
            }
        }
         //把未结束的链表连接到合并后的链表尾部
        if (list1!=null) {
            nListNode.next = list1;
        }
        if (list2!=null) {
            nListNode.next  =list2;
        }
        return head.next;
    }
}
           

2. >另外一种方法就是利用递归的思想：
           

class ListNode {//链表的类定义
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Test1 {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1==null) {
            return list2;
        } else if (list2==null) {
            return list1;
        }       
        while(list1!=null&&list2!=null){
            if (list1.val<list2.val) {
                list1.next = Merge(list1.next, list2);
                return list1;
            }else {
                list2.next = Merge(list1, list2.next);
                return list2;
            }
        }
        return null;
    }
}
           

运行测试：

第一种：

运行时间：19ms

占用内存：12512k

第二种：

运行时间：20ms

占用内存：12488k

总结：

从测试结果来看两种方法的运算资源占用是差不多的。但是第一种算法更有益于加深对链表结构的理解，而且时间复杂度会更加的低，更加的适用于大规模的数据。