[LeetCode] 21. Merge Two Sorted Lists* 解題思路 (Easy)

這題需要把兩個已經排序好的 ListNode 合併並且是排序好的狀態。

LeetCode 題目連結

 

https://leetcode.com/problems/merge-two-sorted-lists/

 

題目

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Accept 作法

這題時間複雜度為 O(n)，原本覺得難，但後來突然想通了之後覺得很簡單。


Runtime: 0 ms
Memory: 39.4 MB

Java 程式碼

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        
        if(l2 == null){
            return l1;
        }
        ListNode cur = l1;
        ListNode cur2 = l2;
        ListNode head = new ListNode(0);
        ListNode p = head;
        while(cur!=null && cur2!=null){
           if(cur.val < cur2.val){
               p.next =cur;
               cur = cur.next;
               
           }else{
               p.next = cur2;
               cur2 = cur2.next;
              
           } 
           
            p = p.next;
        }
        
         if(cur!=null){
            p.next = cur; 
         }
         if(cur2!=null){
            p.next = cur2;
         }
        
        
        return head.next;
    }
}

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題