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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        //{1,2,3},{3,3,3}
        //将右边一个一个往左边插
        ListNode curNode2 = pHead2;
        while (curNode2 != null) {
            ListNode curNode1 = pHead1;
            ListNode lastNode1 = null;
            boolean canInsert = false;
            while (curNode1 != null) {
                if (curNode2.val < curNode1.val) {
                    if (lastNode1 == null) {
                        //比列表1的第一个还要小
                        ListNode tmp2 = curNode2.next;
                        ListNode tmp = pHead1;
                        pHead1 = curNode2;
                        curNode2.next = tmp;
                        curNode2 = tmp2;
                    } else {
                        lastNode1.next = curNode2;
                        ListNode tmp = curNode2.next;
                        curNode2.next = curNode1;
                        curNode2 = tmp;
                    }

                    canInsert = true;
                    break;
                }
                lastNode1 = curNode1;
                curNode1 = curNode1.next;
            }

            if (!canInsert) {
                //第二个这个数，比1所有的都大，直接往后插
                lastNode1.next = curNode2;
                break;
            }
        }

        return pHead1;
    }
}