Brooke

一、題目

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

Example 1:

 

 

 

 

 

 

 

 

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = [] Output: []

Example 3:

Input: list1 = [], list2 = [0] Output: [0]

 

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

 

二、程式作法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution
{
    public ListNode MergeTwoLists(ListNode list1, ListNode list2)
    {
        if (list1 == null)
            return list2;
        else if (list2 == null)
            return list1;

        ListNode res = new ListNode(), curr = res;

        while (list1 != null && list2 != null)
        {
            if (list1.val <= list2.val)
            {
                curr.next = list1;
                list1 = list1.next;
            }
            else
            {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }

        if (list1 == null)
            curr.next = list2;
        else
            curr.next = list1;

        return res.next;
    }
}

 

三、思路筆記

目的為將兩個已排序的鍊結串列，合併成一條。

一開始從兩個串列之開頭各別取出一值來比較，

最小的先挑出來，接下來再從兩個串列之開頭各別取出一值來比較，

直到一方挑完。