leetcode-21. Merge Two Sorted Lists

題目描述(簡單難度)

題目描述:將兩個升序鍊表合併為一個新的 升序 鍊表並返回。新鍊表是通過拼接給定的兩個鍊表的所有節點組成的。

解法一 迭代

遍歷兩個鍊表。

Java

class ListNode{
 int val;
 ListNode next;
 ListNode(int val){
  this.val=val;
 }
}
public class Merge_Two_Sorted_Lists {
 public static ListNode mergertwolists(ListNode l1,ListNode l2) {
  ListNode h=new ListNode(0);
  ListNode ans=h;
  while(l1!=null && l2!=null) {
   if(l1.val<l2.val) {
    h.next=l1;
    h=h.next;
    l1=l1.next;
   }else {
    h.next=l2;
    h=h.next;
    l2=l2.next;
   }
  }
  if(l1==null) h.next=l2;
  if(l2==null) h.next=l1;
  return ans.next;
 }
 public static void main(String args[]) {
  
  ListNode l1=new ListNode(1);
  ListNode p=l1;
  p.next=new ListNode(2);
  p=p.next;
  p.next=new ListNode(4);
  
  ListNode l2=new ListNode(1);
  ListNode q=l2;
  q.next=new ListNode(3);
  q=q.next;
  q.next=new ListNode(4);
  
  ListNode ans=mergertwolists(l1,l2);
  while(ans!=null) {
   System.out.println(ans.val);
   ans=ans.next;
  }
 }
}
時間複雜度：O（m + n）。
空間複雜度：O（1）。
Python
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        l3= ListNode(0)
        h = l3
        while(l1!=None and l2!=None):
            if(l1.val<l2.val):
                h.next=l1
                h=h.next
                l1=l1.next
            else:
                h.next=l2
                h=h.next
                l2=l2.next
        if l1==None:
            h.next=l2
        if l2==None:
            h.next=l1
        return l3.next
在這裡插入圖片描述解法二 遞歸在這裡插入圖片描述Java
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(l2.next,l1);
            return l2;
        }
    }
}
在這裡插入圖片描述Python
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        if l1==None:
            return l2
        if l2==None:
            return l1
        if l1.val < l2.val:
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next=self.mergeTwoLists(l2.next,l1)
            return l2  
在這裡插入圖片描述參考文獻https://www.youtube.com/watch?v=qckKEYP9bBA