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

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
        //处理链表为空的情况
        if (pHead1 == null) return pHead2;
        if (pHead2 == null) return pHead1;
        ListNode sourceNode, destNode;
        //初始节点值小的，为目标链表，大的为需要插入到目标链表的链表
        if (pHead1.val > pHead2.val) {
            sourceNode = pHead1;
            destNode = pHead2;
        } else {
            sourceNode = pHead2;
            destNode = pHead1;
        }
        //System.out.println(sourceNode.val);
        ListNode current = destNode;
        ListNode next = current.next;
        boolean isMerging = true;
        while (isMerging){
            while (current != null) {
                if (next == null){
                    current.next = sourceNode;
                    isMerging = false;
                    break;
                }
                if (next.val < sourceNode.val){
                    current = next;
                    next = next.next;
                }
                else {
                    ListNode tmp = sourceNode;
                    sourceNode = sourceNode.next;
                    current.next = tmp;
                    tmp.next = next;
                    current = tmp;
                    break;
                }
            }
            //System.out.println(sourceNode.val);
            if(sourceNode == null) isMerging = false;
        }
        return destNode;
    }
}

将两个链表分为目的链表和源链表，将源链表插入目的链表

需要处理链表为空的情况

循环体需要注意终止条件，这里使用了一个isMerging变量来控制循环

使用current和next来判断每个位置是否满足插入条件，当满足插入条件时，插入完成后，current应该后移一位（即挪到新插入的节点），而next不需要移动。

需要注意，使用临时节点tmp前，需要先将sourceNode 挪到下一个节点。不然改变tmp的指向也会改变sourceNode的指向