合并两个排序的链表

题目描述

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

题目分析  

　　假如List1中的头节点是小于List2中的，那么新的链表的头节点必将是List1的头节点， 同理对List2也一样，那么在比较完头节点之后，再将List1中的下一个节点再与List2中的头节点比较， 同样谁小谁进入新链表，然后再比较，直到两个链表比较完，故可用非递归或递归两种方式来做。

代码如下：

（1）非递归思想

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode current = new ListNode(-1);//创建一个当前指针
        ListNode root = current;//头结点
        while(list1 != null && list2 != null){//当两个链表都不空时
            if(list2.val >= list1.val){//如果第二个链表当前的数值不小于第一个链表当前的数值
                current.next = list1;//将第一个链表的当前节点加入合并后的链表中
                current = list1;//当前指针后移
                list1 = list1.next;//第一个链表指针后移
            }else{
                current.next = list2;
                current = list2;
                list2 = list2.next;                
            }
        }
        if(list1 != null){
            current.next = list1;
        }
        if(list2 != null){
            current.next = list2;
        }
        return root.next;
    }
}

（2）递归思想

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode head = null;
        if(list1.val <= list2.val){
            head = list1;
            head.next = Merge(list1.next,list2);
        }else{
            head = list2;
            head.next = Merge(list1,list2.next);
        }
        return head;
    }
}

 做题目的时候还是要训练到位，建议先自己想，并且同时实现递归和非递归版本，因为面试的时候一般都会考察。