如何用PHP將兩個已排序的鍊錶合併成一個新的已排序鍊錶。合併後的鍊錶應該透過拼接兩個原始鍊錶的節點來完成?

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

Merge the two lists into 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 !;

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 singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

class ListNode {
    public $val;
    public $next;
    function __construct($val = 0, $next = null) {
        $this->val = $val; // 初始化節點值
        $this->next = $next; // 初始化下一個節點的指針
    }
}

class Solution {
    function mergeTwoLists($list1, $list2) {
        // 創建一個虛擬節點作為合併鏈表的頭部，方便處理
        $dummy = new ListNode(0);
        $current = $dummy;
        
        // 比較並合併節點，直到其中一個鏈表為空
        while ($list1 && $list2) {
            if ($list1->val <= $list2->val) {
                $current->next = $list1; // 將較小值節點連接到當前節點
                $list1 = $list1->next; // 移動第一個鏈表的指針
            } else {
                $current->next = $list2; // 將較小值節點連接到當前節點
                $list2 = $list2->next; // 移動第二個鏈表的指針
            }
            $current = $current->next; // 移動當前指針到下一個節點
        }
        
        // 將剩餘的節點（若有）連接到合併鏈表
        if ($list1) $current->next = $list1;
        if ($list2) $current->next = $list2;
        
        return $dummy->next; // 返回合併後鏈表的頭部
    }
}

這個合併兩個已排序鏈表的算法的時間複雜度為 O(n + m)，其中：
n 是第一個鏈表 (list1) 的節點數。
m 是第二個鏈表 (list2) 的節點數。
原因：
算法通過單一的 while 循環遍歷兩個鏈表，比較並合併節點。
在最壞的情況下，會遍歷 list1 的所有 n 個節點和 list2 的所有 m 個節點。
每個節點只被訪問一次，沒有額外的嵌套循環。
因此，總時間複雜度為 O(n + m)。