当前位置： 面试刷题>> 合并两个有序链表(经典算法150题)
### 题目描述
给定两个按升序排列的有序链表 `list1` 和 `list2`，请将它们合并为一个新的有序链表并返回。合并后的链表是通过拼接两个链表的所有节点（包括节点中的值）并按升序排列的。
### 示例
假设有以下两个链表：
```
list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4
```
合并后的链表应为：
```
1 -> 1 -> 2 -> 3 -> 4 -> 4
```
### PHP 代码示例
```php
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 代码示例
```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 代码示例
```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`）以及一个示例使用场景来验证合并函数的正确性。