合并两个排序的链表

public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        ListNode const_head = new ListNode(0);
        ListNode pre = const_head;
        while(pHead1 != null && pHead2 != null){
            if(pHead1.val <= pHead2.val){
                pre.next = pHead1;
                pHead1 = pHead1.next;
            }else{
                pre.next = pHead2;
                pHead2 = pHead2.next;
            }
            pre = pre.next;
        }
        if(pHead1 != null){
            pre.next = pHead1;
        }
        if(pHead2 != null){
            pre.next = pHead2;
        }
        return const_head.next;
    }

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

        // 算法时间复杂度O(N)，额外空间复杂度O(1)

        // 1.处理边界情况，确保两个链表非空
        if (pHead1 == null) {
            return pHead2;
        }
        if (pHead2 == null) {
            return pHead1;
        }

        // 2.找到两个有序链表头结点中较小的那个，记为targetHead，以target链表为合并的容器，另外一个链表记为source链表
        ListNode targetHead;
        ListNode sourceHead;
        if (pHead1.val <= pHead2.val) {
            targetHead = pHead1;
            sourceHead = pHead2;
        } else {
            targetHead = pHead2;
            sourceHead = pHead1;
        }

        // 3.遍历target链表，针对每个targetCur结点，去source中尝试找到这样一个子序列：
        //      该子序列的所有结点满足 >= targetCur 且 < targetNext(targetCur.next)
        // 若能够找到，则用sourceStart和sourceEnd固定其头和尾的位置，然后将这个子序列完整纳入到target链表中
        ListNode targetCur = targetHead;
        ListNode targetNext = targetHead.next;
        ListNode sourceCur = sourceHead;
        ListNode sourceStart = null;
        ListNode sourceEnd = null;
        while (targetCur != null) {
            System.out.println("targetCur: " + targetCur.val);
            targetNext = targetCur.next;
            if (sourceCur != null && sourceCur.val >= targetCur.val) {
                // 3.1 发现了source链表中有一个 >= targetCur的结点，先记为sourceStart
                // 注意！sourceStart可能已经 >= targetNext的，这种情况是不能将其纳入的，后续要对这种情况做好判断！
                sourceStart = sourceCur;
                System.out.println("发现了一个source链表中比targetCur大的结点：" + sourceStart.val);
                if (targetNext == null) {
                    // 3.2 如果targetCur没有下一个结点，那么sourceStart及其后续结点必然满足要求
                    // 此时就会把从sourceStart开始剩余的source结点全部纳入进来，可以直接结束
                    System.out.println("此时target链表已经到了最后一个结点了");
                    targetCur.next = sourceStart;
                    break;
                }
                
                // 3.3 如果targetCur还有下一个结点，那么必须找到 >= targetCur，且 < targetNext的source结点
                while(sourceCur.next != null && sourceCur.next.val < targetNext.val) {
                    // 找到source链表中一系列比targetCur大，且比targetNext小的source结点，确定它们的头和尾
                    // 注意！sourceCur可能本身已经 >= targetNext了，结束while循环后一定要做对应判断！
                    sourceCur = sourceCur.next;
                }
                sourceEnd = sourceCur;
                // 3.4 此时存在一种可能，即只有唯一的sourceCur，确实 >= target，但是它同时 >= targetNext，此时不应该纳入，应该提前迭代
                if(sourceEnd.val >= targetNext.val) {
                    System.out.println("虽然 >= targetCur，但它同时 >= targetNext，此时也不应该放入");
                    targetCur = targetNext;
                    continue;
                }
                sourceCur = sourceCur.next;
                // 3.5 找到了sourcr链表中满足条件的子序列，且以sourceStart开头，sourceEnd结尾，将他们整体纳入到target链表中
                targetCur.next = sourceStart;
                sourceEnd.next = targetNext;
            }
            // 3.6 target迭代遍历
            targetCur = targetNext;
        }
        return targetHead;
    }
}

    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
                //  输入的是单调递增数列，所以一方为空直接返回无需排序
        if(pHead1 == null){
            return pHead2;
        }
        if(pHead2 == null){
            return pHead1;
        }
                // 创建一个哑节点简化边界处理
        ListNode newList = new ListNode(0);
                // 创建一个排序临时节点，用于记录排序后最新的节点
        ListNode tempList = newList;
        while(pHead1 != null && pHead2 != null){
                        // 比较，将小值标记为排序链表新节点
            if(pHead1.val < pHead2.val){
                tempList.next = pHead1;
                pHead1 = pHead1.next;
                tempList = tempList.next;
            }else{
                tempList.next = pHead2;
                pHead2 = pHead2.next;
                tempList = tempList.next;
            }
        }
                // 将剩余节点接入排序节点末端
        if(pHead1 != null){
            tempList.next = pHead1;
        }
        if(pHead2 != null){
            tempList.next = pHead2;
        }
        return newList.next;
    }

参考代码（Java版本）

迭代

public ListNode Merge (ListNode pHead1, ListNode pHead2) {
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (pHead1 != null && pHead2 != null) {
        if (pHead1.val <= pHead2.val) {
            cur.next = pHead1;
            pHead1 = pHead1.next;
        } else {
            cur.next = pHead2;
            pHead2 = pHead2.next;
        }
        cur = cur.next;
    }
    if (pHead1 != null) {
        cur.next = pHead1;
    }
    if (pHead2 != null) {
        cur.next = pHead2;
    }
    return dummy.next;
}

递归

public ListNode Merge(ListNode pHead1, ListNode pHead2) {
    if (pHead1 == null) {
        return pHead2;
    }
    if (pHead2 == null) {
        return pHead1;
    }
    if (pHead1.val <= pHead2.val) {
        pHead1.next = Merge(pHead1.next, pHead2);
        return pHead1;
    } else {
        pHead2.next = Merge(pHead1, pHead2.next);
        return pHead2;
    }
}

public ListNode Merge (ListNode pHead1, ListNode pHead2) {
    // write code here
    ListNode list = new ListNode(0); //定义一个头节点
    ListNode p = list; //工作指针
    //遍历链表pHead1和pHead2，让节点值更小的节点挂到list上
    while(pHead1 != null && pHead2 != null){
        if(pHead1.val <= pHead2.val){
            p.next = pHead1;
            pHead1 = pHead1.next;
        }else{
            p.next = pHead2;
            pHead2 = pHead2.next;
        }
        p = p.next;
    }
    //让还没有遍历完的节点继续遍历挂到list上
    while(pHead1 != null){
        p.next = pHead1;
        pHead1 = pHead1.next;
        p = p.next;
    }
    while(pHead2 != null){
        p.next = pHead2;
        pHead2 = pHead2.next;
        p = p.next;
    }
    return list.next;
}

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
  
    ListNode dump = new ListNode(-1); // 用于返回
  
    ListNode pre = dump;
  
    if(pHead1 == null&&pHead2==null){
  
        return null;
  
    }
  
    if(pHead1 == null&&pHead2!=null){
  
        return pHead2;
  
    }
  
     if(pHead1 != null&&pHead2==null){
  
        return pHead1;
  
    }
  
    while(pHead1!=null&&pHead2!=null){
  
        if(pHead1.valpHead2.val){
  
            pre.next = pHead1;
  
            pre = pHead1;
  
            pHead1 = pHead1.next;
  
        }else{
  
            pre.next = pHead2;
  
            pre = pHead2;
  
            pHead2 = pHead2.next;
  
        }
  
    }
  
    if(pHead1 == null){
  
        pre.next = pHead2;
  
    }
  
    if(pHead2 == null){
  
         pre.next = pHead1;
  
    }
  
    return dump.next;

  }

}

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) {
        if (pHead1 == null) return pHead2;
        if (pHead2 == null) return pHead1;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val > pHead2.val) {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            } else {
                cur.next = pHead1;
                pHead1 = pHead1.next;
            }
            cur = cur.next;
        }
        if (pHead1 != null) {
            cur.next = pHead1;
        }

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

        return dummy.next;
    }
}

// 简单易懂，双指针比较大小
public class Solution {

    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // 最后返回的链表
        ListNode pre = new ListNode(-1);
        // 操作指针
        ListNode curPre = pre;
        
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;

        // 遍历比较大小，小的连接上
        while(cur1 != null && cur2 != null ){
            if(cur1.val < cur2.val){
                curPre.next = cur1;
                cur1 = cur1.next;
            }else{
                curPre.next = cur2;
                cur2 = cur2.next;
            }
            curPre = curPre.next;
        }

        // 把剩余的链接上
        if(cur1 != null){
            curPre.next = cur1;
        }
        if(cur2 != null){
            curPre.next = cur2;
        }
        
        return pre.next;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        // 新链表的虚拟头节点
        ListNode dummy = new ListNode(0);
        // 当前节点
        ListNode cur = dummy;
        // 链表1
        ListNode pre1 = pHead1;
        // 链表2
        ListNode pre2 = pHead2;
        while (pre1 != null && pre2 != null) {
            // 表1头节点的值<=表2头节点的值
            if (pre1.val <= pre2.val) {
                // 将表1的头节点拼接到新表末尾
                cur.next = pre1;
                // 删除表1的头节点，即头结点后移一位
                pre1 = pre1.next;
            // 表2头节点的值>表2头节点的值时，对表2进行与表1同样的操作
            } else {
                cur.next = pre2;
                pre2 = pre2.next;
            }
            // dummy表的当前节点（即末尾节点）后移一位
            cur = cur.next;            
        }
        // 表1表2其中一个完成所有节点拼接到dummy表后，表1表2中有一个还有剩余元素，此时将剩余节点拼接到dummy表中
        cur.next = pre1 != null ? pre1 : pre2;
        // 返回dummy所指向的节点
        return dummy.next;
    }
}

public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        if(pHead1 == null){
            return pHead2;
        }
        if(pHead2 == null){
            return pHead1;
        }
        ListNode result = new ListNode(0);
        ListNode nextNode = new ListNode(0);
        result.next = nextNode;
        while(pHead1 != null && pHead2 != null){
            if(pHead1.val > pHead2.val){
                nextNode.val = pHead2.val;
                pHead2 = pHead2.next;
                if(pHead2 != null){
                    nextNode.next = new ListNode(0);
                    nextNode = nextNode.next;
                }
            }else{
                nextNode.val = pHead1.val;
                pHead1 = pHead1.next;
                if(pHead1 != null){
                    nextNode.next = new ListNode(0);
                    nextNode = nextNode.next;
                }
            }
        }
        if(pHead1 != null){
            nextNode.next = pHead1;
        }else{
            nextNode.next = pHead2;
        }
        return result.next;
    }