题目描述（简单难度）

21. Merge Two Sorted Lists - 图1

合并两个有序链表。

解法一 迭代

遍历两个链表。

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

时间复杂度：O（m + n）。

空间复杂度：O（1）。

解法二 递归

参考这里

  1. ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  2.     if(l1 == null) return l2;
  3.     if(l2 == null) return l1;
  5.     if(l1.val < l2.val) {
  6.         l1.next = mergeTwoLists(l1.next, l2);
  7.         return l1;
  8.     } else {
  9.         l2.next = mergeTwoLists(l2.next, l1);
  10.         return l2;
  11.     }
  12. }

时间复杂度：

空间复杂度：

总

递归看起来，两个字，优雅！但是关于递归的时间复杂度，空间复杂度的求法，先留个坑吧。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情