21. 合并两个有序链表

image.png

迭代

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：38 MB, 在所有 Java 提交中击败了9.27% 的用户

  1. class Solution {
  2.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  3.         if (l1 == null) return l2;
  4.         if (l2 == null) return l1;
  6.         ListNode temp = new ListNode(0);
  7.         ListNode cur = temp;
  8.         while (l1 != null && l2 != null) {
  9.             if (l1.val < l2.val) {
  10.                 cur.next = l1;
  11.                 l1 = l1.next;
  12.             } else {
  13.                 cur.next = l2;
  14.                 l2 = l2.next;
  15.             }
  16.             cur = cur.next;
  17.         }
  19.         if (l1 != null) cur.next = l1;
  20.         if (l2 != null) cur.next = l2;
  22.         return temp.next;
  23.     }
  24. }

递归

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：37.8 MB, 在所有 Java 提交中击败了64.76% 的用户

class Solution {
    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;
        }
    }
}