链表.合并排序链表
最新回答
柠檬你个思密达
2026-07-19 04:45:50
### 迭代解法（归并排序）
此方法结合了归并排序的基本思想，通过迭代将两个已排序的链表合并为一个排序链表。核心步骤包括设置虚拟头节点、比较链表中的元素并连接较小的元素。
**算法流程：**
1. **初始化虚拟头节点**：设置一个虚拟头节点，用于构建合并后的链表。
2. **迭代比较**：比较两个链表的当前节点的值，将较小者连接到合并后的链表中。
3. **前进指针**：将指针移动到被选元素的下一个节点。
4. **重复步骤**：直到一个链表结束。
5. **连接剩余部分**：将另一个链表的剩余部分连接到合并链表的末尾。
**Java实现版本一**
java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode 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;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
### 递归解法
递归方法利用链表的自然结构，直接比较两个链表的头节点，并将较小者作为新链表的头节点。该方法简洁明了，易于理解。
**Java实现版本二**
java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
### 易错点
1. **空指针异常**：在开始比较之前，确保链表非空。
2. **边界条件**：递归终止条件处理不当会导致无限递归。
3. **链表操作**：确保在操作链表时正确处理节点的连接和断开。
### 结论
迭代和递归方法各有优缺点。迭代方法代码更直观，易于理解，但可能在性能上略逊于递归。递归方法简洁高效，但实现时需特别注意边界条件和空指针异常的处理。选择方法时，应根据具体需求和场景来决定。
热门标签
