合并两个排序的链表

问题描述

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

思路

第一种思路

对其中一个进行循环，然后遍历另一个，如果发现有在中间的，就查到里面。这样将一个循环完毕后就能生成一个合并的链表了。

代码

第一种思路

public class Main {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(7);
        ListNode listNode4 = new ListNode(8);
        ListNode listNode5 = new ListNode(9);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode listNode6 = new ListNode(3);
        ListNode listNode7 = new ListNode(4);
        ListNode listNode8= new ListNode(5);
        ListNode listNode9 = new ListNode(6);
        ListNode listNode10 = new ListNode(11);
        listNode6.next = listNode7;
        listNode7.next = listNode8;
        listNode8.next = listNode9;
        listNode9.next = listNode10;
        ListNode a = Merge(listNode1,listNode6);
    }
    public static ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null && list2==null) return null;
        if(list1==null ) return list2;
        if(list2==null ) return list1;
        while (list1!=null)
        {
            ListNode list1Node  = new ListNode(list1.val);
            list2 =  loop(list2,list1Node);
            list1 = list1.next;
        }
    return list2;
    }
    private static ListNode loop(ListNode list2,ListNode list1Node)
    {
        ListNode p1 = list2;
        ListNode p2 = list2.next;
        if(p2==null)
        {
            if(p1.val>=list1Node.val)
            {
                list1Node.next = p1;
                list2 = list1Node;
            }
            else  if(p1.val<=list1Node.val)
            {
                list2.next = list1Node;
            }
            return list2;
        }
        while (p1!=null)
        {
            if(list1Node.val>=p1.val&& list1Node.val<=p2.val)
            {
                p1.next = list1Node;
                list1Node.next = p2;
                break;
            }
            if(list1Node.val>=p2.val && p2.next==null)
            {
                p2.next = list1Node;
                break;
            }
            if(list1Node.val <= p1.val)
            {
                list1Node.next = p1;
                list2 = list1Node;
                break;
            }
            if(p2.next!=null)
            {
                p1 = p2;
                p2 = p2.next;
            }
            else p1 = null;
        }
        return list2;
    }
}
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}