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

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、遍历2个链表,把新链表的next 指向值小的节点,同时把值小的节点后移,
        //    把新链表的当前指针也后移动
        //    再次比较值小的链表后一个节点和值大的链表当前节点的大小
        // 3、如果某个链表移到最后没有节点了，则把新链表当前指针的next指向另外一个链表

        ListNode cur = new ListNode(-1);
        ListNode root = cur;

       while(pHead1 != null || pHead2 != null){

        if(pHead1 == null){
            cur.next = pHead2;
            break;
        }

        if(pHead2 == null){
            cur.next = pHead1;
            break;
        }

        int val1 = pHead1.val;
        int val2 = pHead2.val;

        if(val1>val2){
            cur.next = pHead2;
            pHead2 = pHead2.next;
        }else{
            cur.next = pHead1;
            pHead1 = pHead1.next;
        }

        cur = cur.next;
       }

       return root.next;
    }
}