题目描述

合并两个已排序的链表，并返回合并后的排序链表。链表中的元素是唯一的，并且按升序排列。每个节点都有一个 val（节点值）和一个 next（指向下一个节点的指针或 null，如果节点是链表的最后一个节点）。

示例

假设我们有两个链表 1 -> 2 -> 4 和 1 -> 3 -> 4，合并后的链表应该是 1 -> 1 -> 2 -> 3 -> 4 -> 4（注意，合并后的链表可能包含重复的元素，但题目要求每个节点值都是唯一的，这里的重复是为了说明合并过程，实际合并时可能需要去重，但在此题目中我们直接合并即可）。

解题思路

使用双指针法来合并两个链表。创建一个新的头节点（dummy head）来简化边界条件的处理，并分别使用两个指针遍历两个输入链表。比较两个指针指向的节点的值，将较小值的节点连接到结果链表的末尾，并移动对应的指针。重复这个过程，直到其中一个链表遍历完成。之后，将剩余链表直接连接到结果链表的末尾。

PHP 示例代码

<?php

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

function mergeTwoLists($l1, $l2) {
    $dummy = new ListNode(0);
    $current = $dummy;

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

    if ($l1 !== null) {
        $current->next = $l1;
    }

    if ($l2 !== null) {
        $current->next = $l2;
    }

    return $dummy->next;
}

// 示例用法
$l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
$l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
$merged = mergeTwoLists($l1, $l2);

// 打印合并后的链表
function printList($head) {
    while ($head !== null) {
        echo $head->val . " ";
        $head = $head->next;
    }
    echo "\n";
}

printList($merged);

?>

Python 示例代码

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

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    current = dummy

    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    current.next = l1 if l1 is not None else l2

    return dummy.next

# 示例用法
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
merged = mergeTwoLists(l1, l2)

# 打印合并后的链表
def printList(head):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

printList(merged)

JavaScript 示例代码

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

function mergeTwoLists(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;

    while (l1 && l2) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    if (l1) {
        current.next = l1;
    }

    if (l2) {
        current.next = l2;
    }

    return dummy.next;
}

// 示例用法
let l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
let l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
let merged = mergeTwoLists(l1, l2);

// 打印合并后的链表
function printList(head) {
    let current = head;
    while (current) {
        console.log(current.val);
        current = current.next;
    }
}

printList(merged);

// 码小课网站中有更多相关内容分享给大家学习