题目描述

给定两个按升序排列的有序链表 list1 和 list2，请将它们合并为一个新的有序链表并返回。合并后的链表是通过拼接两个链表的所有节点（包括节点中的值）并按升序排列的。

示例

假设有以下两个链表：

list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

合并后的链表应为：

1 -> 1 -> 2 -> 3 -> 4 -> 4

PHP 代码示例

<?php

class ListNode {
    public $val;
    public $next;
    
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function mergeTwoLists($list1, $list2) {
    $dummy = new ListNode(0); // 创建一个哑节点作为新链表的头
    $current = $dummy; // 当前指针，用于遍历新链表

    while ($list1 !== null && $list2 !== null) {
        if ($list1->val < $list2->val) {
            $current->next = $list1;
            $list1 = $list1->next;
        } else {
            $current->next = $list2;
            $list2 = $list2->next;
        }
        $current = $current->next;
    }

    // 如果某个链表还有剩余节点，直接将剩余部分连接到新链表后面
    if ($list1 !== null) {
        $current->next = $list1;
    }
    if ($list2 !== null) {
        $current->next = $list2;
    }

    return $dummy->next; // 返回哑节点的下一个节点，即新链表的头
}

// 示例使用
$list1 = new ListNode(1);
$list1->next = new ListNode(2);
$list1->next->next = new ListNode(4);

$list2 = new ListNode(1);
$list2->next = new ListNode(3);
$list2->next->next = new ListNode(4);

$mergedList = mergeTwoLists($list1, $list2);

// 打印合并后的链表
while ($mergedList !== null) {
    echo $mergedList->val . ' ';
    $mergedList = $mergedList->next;
}
// 输出: 1 1 2 3 4 4
?>

Python 代码示例

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1, list2):
    dummy = ListNode()
    current = dummy

    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    current.next = list1 if list1 is not None else list2
    return dummy.next

# 示例使用
list1 = ListNode(1, ListNode(2, ListNode(4)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
merged_list = mergeTwoLists(list1, list2)

# 打印合并后的链表
while merged_list:
    print(merged_list.val, end=' ')
    merged_list = merged_list.next
# 输出: 1 1 2 3 4 4

JavaScript 代码示例

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function mergeTwoLists(list1, list2) {
    let dummy = new ListNode(0);
    let 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;
    }

    current.next = list1 ? list1 : list2;
    return dummy.next;
}

// 示例使用
let list1 = new ListNode(1, new ListNode(2, new ListNode(4)));
let list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
let mergedList = mergeTwoLists(list1, list2);

// 打印合并后的链表
let current = mergedList;
while (current) {
    console.log(current.val);
    current = current.next;
}
// 输出: 1 1 2 3 4 4

以上代码示例展示了如何在PHP、Python和JavaScript中合并两个有序链表。每个示例都包含了创建链表节点类（ListNode）、合并函数（mergeTwoLists）以及一个示例使用场景来验证合并函数的正确性。