当前位置： 面试刷题>> 合并两个排序链表 (经典算法题500道)
### 题目描述
合并两个已排序的链表，并返回合并后的排序链表。链表中的元素是唯一的，并且按升序排列。每个节点都有一个 `val`（节点值）和一个 `next`（指向下一个节点的指针或 `null`，如果节点是链表的最后一个节点）。
### 示例
假设我们有两个链表 `1 -> 2 -> 4` 和 `1 -> 3 -> 4`，合并后的链表应该是 `1 -> 1 -> 2 -> 3 -> 4 -> 4`（注意，合并后的链表可能包含重复的元素，但题目要求每个节点值都是唯一的，这里的重复是为了说明合并过程，实际合并时可能需要去重，但在此题目中我们直接合并即可）。
### 解题思路
使用双指针法来合并两个链表。创建一个新的头节点（dummy head）来简化边界条件的处理，并分别使用两个指针遍历两个输入链表。比较两个指针指向的节点的值，将较小值的节点连接到结果链表的末尾，并移动对应的指针。重复这个过程，直到其中一个链表遍历完成。之后，将剩余链表直接连接到结果链表的末尾。
### PHP 示例代码
```php
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 示例代码
```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 示例代码
```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);
// 码小课网站中有更多相关内容分享给大家学习
```