[LeetCode]Merge Two Sorted Lists

Merge Two Sorted Lists

合併兩個已排序的鍊表

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]

解法

一開始的想法是取出兩個表的值進行排序，最後再重新產出新的鏈表。

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2) {
        $arr_dic = array();

        while (true) {
            # 取出兩陣列的值
            if (isset($list1->val))
                $arr_dic[] = $list1->val;
            if (isset($list2->val))
                $arr_dic[] = $list2->val;

            $list1 = $list1->next;
            $list2 = $list2->next;

            if ($list1 == '' && $list2 == '')
                break;
        }

        # 排序
        sort($arr_dic);

        # 重新產出鏈結
        $result_list = new ListNode();
        $res = $result_list;
        foreach ($arr_dic as $num) {
            $res->next = new ListNode($num);
            if (count($arr_dic) > 0)
                $res = $res->next;
        }

        return $result_list->next;
    }
}

而另一種解法是利用遞迴，解法更簡潔有力。

class Solution {

    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2) {
        if ($list1 == '')
            return $list2;
        if ($list2 == '')
            return $list1;

        if ($list1->val < $list2->val) {
            $list1->next = $this->mergeTwoLists($list1->next, $list2);
            return $list1;
        } else {
            $list2->next = $this->mergeTwoLists($list1, $list2->next);
            return $list2;
    }
}