()迭代方式思路如下:

  • 定义一个函数,该函数返回合并后链表的头结点,参数是两个待合并的链表
  • 首先判断这两个链表是否为空,一个为空返回另一个
  • 比较这两个链表的首节点,谁最小谁就是新链表的头结点
  • 定义一个用于新链表插入元素的临时变量,初始值是上一步找到的头结点
  • 开启while循环,条件是两个链表都不为空(&&),也就是有一个为空就停止循环
  • 循环结束后,判断哪一个链表为空,一个为空,新链表尾结点的下一个节点就是另一个不为空的链表的当前节点
//两个有序链表的合并
public static LinkedNode merge(LinkedNode l1, LinkedNode l2){
    LinkedNode newHead = null;

    //判断是否为空链表
    if(l1 == null){
        return l2;
    }
    if(l2 == null){
        return l1;
    }

    //选择新链表的头结点
    if(l1.value <= l2.value){
        newHead = l1;
        l1 = l1.next;
    }else{
        newHead = l2;
        l2 = l2.next;
    }

    LinkedNode temp = newHead;
    //循环遍历两个链表
    while (l1 != null && l2 != null){
        if(l1.value <= l2.value){
            temp.next = l1;
            l1 = l1.next;
        }else{
            temp.next = l2;
            l2 = l2.next;
        }

        temp = temp.next;
    }

    if(l1 == null ){
        temp.next = l2;
    }
    if(l2 == null){
        temp.next = l1;
    }

    return newHead;
}