合并两个有序链表
题目要求
合并两个已排序的链表为一个新的排序链表。具体来说，你需要按照升序将两个链表中的节点连接起来，形成一个新的链表。
解题思路
合并两个升序链表的基本思路是使用双指针技术，分别指向两个链表的头部，然后比较两个指针所指向的节点的值，将较小值的节点添加到新链表中，并移动该指针到下一个节点。重复这个过程，直到某一个链表的指针到达链表末尾。最后，将未结束的链表直接连接到新链表的末尾。
步骤如下：
- 初始化一个新的链表头节点，这将作为合并后链表的哨兵节点，以便于操作。
- 创建两个指针，分别指向两个链表的头部。
- 比较两个指针所指向的节点的值，将较小值的节点接在新链表的最后一个节点后面，并将对应的指针后移一位。
- 如果一个链表的指针先到达末尾，将另一个链表的剩余部分接在新链表后面。
- 由于第一步中创建了一个哨兵节点，最终返回哨兵节点的下一个节点作为合并后的链表的头节点。
注意事项：
- 在实际操作中，为了简化代码，通常会使用一个哨兵节点（dummy node），这样可以避免对头节点进行特殊处理。
- 在循环过程中，需要检查两个链表的指针是否已经到达链表末尾。
- 合并完成后，确保断开与原链表的连接，这样不会影响原链表的结构。
Golang 版本
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{} // 创建哨兵节点
current := dummy
// 遍历两个链表，直到至少一个到达末尾
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
// 如果l1还有剩余节点，直接连接到新链表的末尾
if l1 != nil {
current.Next = l1
}
// 如果l2还有剩余节点，直接连接到新链表的末尾
if l2 != nil {
current.Next = l2
}
return dummy.Next // 返回哨兵节点的下一个节点，即合并后的链表的头节点
}
这段代码定义了一个ListNode结构体，用于表示链表节点。mergeTwoLists函数接受两个指向ListNode的指针l1和l2作为参数，返回一个新的合并后的链表的头节点。函数内部使用了一个哨兵节点来简化链表操作，并通过比较节点值来决定节点的合并顺序。最后，函数处理了其中一个链表先遍历完的情况，将另一个链表剩余部分直接连接到新链表末尾。
C++版本
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0); // 创建哨兵节点
ListNode *current = dummy;
// 遍历两个链表，直到至少一个到达末尾
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
// 如果l1还有剩余节点，直接连接到新链表的末尾
if (l1 != nullptr) {
current->next = l1;
}
// 如果l2还有剩余节点，直接连接到新链表的末尾
if (l2 != nullptr) {
current->next = l2;
}
ListNode *mergedHead = dummy->next;
delete dummy; // 删除哨兵节点
return mergedHead; // 返回合并后的链表的头节点
}
};
这段 C++代码定义了一个ListNode结构体和一个Solution类。Solution类中的mergeTwoLists方法接受两个指向ListNode的指针l1和l2作为参数，并返回一个指向新合并链表头节点的指针。方法中使用了一个哨兵节点来简化链表操作，并通过循环比较节点值来决定节点的合并顺序。最后，方法处理了其中一个链表先遍历完的情况，并在返回前删除了哨兵节点以避免内存泄漏。
Python 版本
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
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 or l2
return dummy.next
这段 Python 代码定义了一个ListNode类用于表示链表节点，以及一个Solution类。Solution类中的mergeTwoLists方法接受两个ListNode实例l1和l2作为参数，并返回一个新的合并后的链表的头节点。方法中使用了一个哨兵节点（dummy node）来简化链表操作，并通过循环比较节点值来决定节点的合并顺序。最后，方法处理了其中一个链表先遍历完的情况，将另一个链表剩余部分直接连接到新链表末尾。
Java 版本
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
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;
}
// Attach the remaining elements
if (l1 != null) {
current.next = l1;
} else if (l2 != null) {
current.next = l2;
}
return dummy.next;
}
}
这段 Java 代码定义了一个ListNode类用于表示链表节点，以及一个Solution类。Solution类中的mergeTwoLists方法接受两个ListNode对象l1和l2作为参数，并返回一个新的合并后的链表的头节点。方法中使用了一个哨兵节点（dummy node）来简化链表操作，并通过循环比较节点值来决定节点的合并顺序。最后，方法处理了其中一个链表先遍历完的情况，将另一个链表剩余部分直接连接到新链表末尾。
Rust 版本
#![allow(unused)] fn main() { // Definition for singly-linked list. #[derive(PartialEq, Eq, Clone, Debug)] pub struct ListNode { pub val: i32, pub next: Option<Box<ListNode>>, } impl ListNode { #[inline] fn new(val: i32) -> Self { ListNode { next: None, val, } } } impl Solution { pub fn merge_two_lists( l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>, ) -> Option<Box<ListNode>> { let mut dummy = Some(Box::new(ListNode::new(0))); let mut current = &mut dummy; let mut l1 = l1; let mut l2 = l2; while let (Some(n1), Some(n2)) = (&l1, &l2) { if n1.val < n2.val { if let Some(next) = l1 { current.as_mut().unwrap().next = Some(next); l1 = current.as_mut().unwrap().next.as_mut().unwrap().next.take(); } } else { if let Some(next) = l2 { current.as_mut().unwrap().next = Some(next); l2 = current.as_mut().unwrap().next.as_mut().unwrap().next.take(); } } current = &mut current.as_mut().unwrap().next; } if l1.is_some() { current.as_mut().unwrap().next = l1; } else if l2.is_some() { current.as_mut().unwrap().next = l2; } dummy.unwrap().next } } }
这段 Rust 代码定义了一个ListNode结构体用于表示链表节点，并实现了一个new函数用于创建新节点。Solution结构体中的merge_two_lists函数接受两个Option<Box<ListNode>>类型的参数l1和l2，表示两个可能为空的链表，并返回一个合并后的链表。函数中使用了一个哨兵节点（dummy node）来简化链表操作，并通过循环比较节点值来决定节点的合并顺序。最后，函数处理了其中一个链表先遍历完的情况，将另一个链表剩余部分直接连接到新链表末尾。
总结
上面给出了使用不同编程语言实现的合并两个升序链表的解法。无论是使用哪种语言，基本的思路都是一致的：
- 创建一个哨兵节点（dummy node）来简化链表操作。
- 使用循环和条件判断来比较两个链表节点的值，将较小值的节点连接到新链表中。
- 处理其中一个链表先遍历完的情况，将另一个链表剩余部分直接连接到新链表末尾。
这些解法展示了如何在不同的编程语言中使用类、结构体和指针等不同的特性来实现相同的算法逻辑。