题解 | #合并两个排序的链表#

合并两个排序的链表

http://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337

递归算法

对于两个链表 list1 和 list2 首先找出两个链表初始位置的较大节点和较小节点，将较大节点所在列表标记为链表 A，将较小节点所在链表标记为链表 B，将较大节点插入到链表b中的合适位置，则从链表 B 起始节点到较大节点处标记为已经插入完成的链表是，将插入完成后的链表 B 中较大节点插入位置的下一个节点至链表 B 的结尾标记为新的 list1，将链表 A 中较大节点的下一个节点开始直至链表 A 的结尾标记为 list2，将 list1 和 list2 做为初始列表进行递归调用，直至二者之一到达末尾，返回另一个链表的剩余节点头节点

Java代码：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
        public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode bList = null;
        ListNode slist = null;
        ListNode nxtBlist;
        ListNode nxtSlist;
        ListNode reSlist;
        if (list1 == null || list2 == null) {
            if (list1 == null){
                return list2;
            }else if (list2 == null){
                return list1;
            }else {
                return null;
            }
        }
        //找出较大list1是否大于list2，大于返回1不大于返回-1相等返回0
        int compares = compares(list1, list2);
        if (compares==1){
            bList=list1;
            slist=list2;
        }else if (compares==-1){
            bList=list2;
            slist=list1;
        }else {
            bList=list1;
            slist=list2;
        }
        reSlist=slist;
        while (true){
            //判断较大节点是否在较小节点和较小节点的下一个节点之间
            if (slist.next==null||bList.val<slist.next.val){
                break;
            }
            slist=slist.next;
        }
        //条件满足插入
        nxtBlist=bList.next;
        nxtSlist=slist.next;
        slist.next=bList;
        bList.next=nxtSlist;

        //插入完成
        bList.next = Merge(nxtSlist, nxtBlist);
        return reSlist;
    }

    public int compares(ListNode list1, ListNode list2){
        if (list1.val>list2.val){
            return 1;
        }else if (list1.val<list2.val){
            return -1;
        }else {
            return 0;
        }
    }
}