合并两个有序链表

/**

• 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

• 示例：

• 输入：1->2->4, 1->3->4

• 输出：1->1->2->3->4->4

• 来源：力扣（LeetCode）

• 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
  /
  public class MergedSortList {
  /*

  • 递归
  • 首先考虑边界情况。 特殊的，如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止。
    *复杂度分析
  • 时间复杂度：O(n + m) 因为每次调用递归都会去掉 l1 或者 l2 的头元素（直到至少有一个链表为空），函数 mergeTwoList 中只会遍历每个元素一次。所以，时间复杂度与合并后的链表长度为线性关系。
  • 空间复杂度：O(n + m)调用 mergeTwoLists 退出时 l1 和 l2 中每个元素都一定已经被遍历过了，所以 n + m个栈帧会消耗 O(n + m)的空间。
  • @param l1
  • @param l2
  • @return
    */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1==null) return l2;
    if(l2==null) return l1;
    if(l1.val<l2.val){
    l1.next=mergeTwoLists(l1.next,l2);
    return l1;
    }else{
    l2.next=mergeTwoLists(l1,l2.next);
    return l2;
    }

  }

  /**

  • 方法 2：迭代
  • 首先，我们设定一个哨兵节点 "prehead" ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前位置的值小于等于 l2 ，我们就把 l1 的值接在 prev 节点的后面同时将 l1 指针往后移一个。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都把 prev 向后移一个元素。
  • 在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表。
    *时间复杂度：O(n + m)。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， while 循环的次数等于两个链表的总长度。所有其他工作都是常数级别的，所以总的时间复杂度是线性的。
  • 空间复杂度：O(1)。迭代的过程只会产生几个指针，所以它所需要的空间是常数级别的。
  • @param l1
  • @param l2
  • @return
    */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(-1);
    ListNode head=result;
    while(l1!=null&&l2!=null){
    if(l1.val<=l2.val){
    result.next=l1;
    l1 = l1.next;
    }else {
    result.next=l2;
    l2=l2.next;
    }
    result = result.next;
    }
    result.next = l1==null?l2:l1;
    return head.next;

  }
  class ListNode{
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
  }

  public static void main(String[] args){
  MergedSortList mergedSortList = new MergedSortList();
  MergedSortList.ListNode l1One = mergedSortList.new ListNode(1);
  MergedSortList.ListNode l1Two = mergedSortList.new ListNode(2);
  MergedSortList.ListNode l1Three = mergedSortList.new ListNode(4);
  l1One.next=l1Two;
  l1Two.next=l1Three;

   MergedSortList.ListNode l2One = mergedSortList.new ListNode(1);
   MergedSortList.ListNode l2Two = mergedSortList.new ListNode(3);
   MergedSortList.ListNode l2Three = mergedSortList.new ListNode(4);
   l2One.next=l2Two;
   l2Two.next=l2Three;
   ListNode result = mergedSortList.mergeTwoLists1(l1One,l2One);
   while(result!=null){
       System.out.println(result.val);
       result=result.next;
   }
  

  }
  }