21.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

【思路】

鏈式實在有點頭痛但因為這題的鏈式都已經排序好了

所以只要比較雙方當下值並用一個暫存Node來存放即可

【解法】

☆JAVA

請看下面說明，我比較習慣這樣理解，雖然慢但可以懂:)

用l1=> [1->2->4] , l2=> [1->3->4] 的範例來講

初始值:
    cur.val = -1;
    cur.next = null;
第一次: [1 vs 1]
    走下面判斷式
    cur.next = l2    (l2      => val=1 , next = l2.next[3])
    l2 = l2.next    (l2.next => val=3 , next = l2.next[4])
    cur = l2
    {cur=> -1->1}
第二次: [1 vs 3]
    走上面判斷式
    cur.next = l1    (l1      => val=1 , next = l1.next[2])
    l1 = l1.next    (l1.next => val=2 , next = l1.next[4])
    cur = l1
    {cur=> -1->1->1}
第三次: [2 vs 3]
    走上面判斷式
    cur.next = l1    (l1      => val=2 , next = l1.next[4])
    l1 = l1.next    (l1.next => val=4 , next = null)
    cur = l1
    {cur=> -1->1->1->2}
第四次: [4 vs 3]
    走下面判斷式
    cur.next = l2    (l2      => val=3 , next = l1.next[4])
    l2 = l2.next    (l2.next => val=4 , next = null)
    cur = l2
    {cur=> -1->1->1->2->3}
..
..
cur.next=(l1!=null)?l1:l2;
之後就如上述概念 有其中個為null的話 就會用next串剩下的    

{cur=> -1->1->1->2->3->4->4}
所以最後才會return next
{cur=> 1->1->2->3->4->4}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode(-1);        #初始化新的ListNode
        ListNode dummy=cur;                     #暫存ListNode , 這邊要回覆用的
        while(l1!=null&&l2!=null){              #防呆判斷
            if(l1.val<l2.val) {                 #判斷 l1.val<l2.val
                cur.next=l1;                        #初始化的 Cur.nextNode = 比較小的那方
                l1=l1.next;                         #比較小的那方 換下一個nextNode
            }else{                              #Else
                cur.next=l2;                        #初始化的 Cur.nextNode = 比較小的那方      
                l2=l2.next;                         #比較小的那方 換下一個nextNode
            }  
            cur=cur.next;                       #換下一個
        }  
        cur.next=(l1!=null)?l1:l2;  
        return dummy.next;  
    }
}

☆Python

Jave 比較好做 , 偷懶一下 XD

21. Merge Two Sorted Lists