将两个链表合并成一个链表（把两个链表合并成一个链表）

简介：

合并两个链表成为一个链表是一种常见的链表操作。在这个操作中，我们需要将两个已经排好序的链表合并成一个新的链表，使得新链表仍然保持有序。本文将介绍如何实现这个操作。

多级标题：

1.问题描述

2.算法思路

2.1 递归法

2.2 迭代法

3.实现代码

4.测试样例及结果

5.总结

内容详细说明：

1.问题描述：

给定两个已经排好序的链表，我们需要将它们合并成一个新的链表，并使得新链表中的元素保持有序。

2.算法思路：

我们将介绍两种常见的算法思路来解决这个问题：递归法和迭代法。

2.1 递归法：

递归法是一种自顶向下的算法思路。具体步骤如下：

- 首先比较两个链表的头节点，将较小的节点作为新链表的头节点。

- 然后递归地将较小节点的next指针指向两个链表剩余部分合并后的链表头节点。

- 最后返回合并后的链表头节点。

2.2 迭代法：

迭代法是一种自底向上的算法思路。具体步骤如下：

- 首先创建一个新链表，并初始化指向新链表的指针。

- 然后比较两个链表的头节点，将较小的节点添加到新链表中，并更新指向新链表的指针和对应链表的指针。

- 重复上一步，直到一个链表为空。

- 将另一个非空链表的剩余部分添加到新链表尾部。

- 最后返回新链表的头节点。

3.实现代码：

下面是使用Python实现上述两种算法的示例代码：

```python

# 递归法

def mergeTwoListsRecursive(l1, l2):

if not l1:

return l2

elif not l2:

return l1

elif l1.val < l2.val:

l1.next = mergeTwoListsRecursive(l1.next, l2)

return l1

else:

l2.next = mergeTwoListsRecursive(l1, l2.next)

return l2

# 迭代法

def mergeTwoListsIterative(l1, l2):

dummy = ListNode(0)

curr = dummy

while l1 and l2:

if l1.val < l2.val:

curr.next = l1

l1 = l1.next

else:

curr.next = l2

l2 = l2.next

curr = curr.next

curr.next = l1 if l1 else l2

return dummy.next

```

4.测试样例及结果：

下面给出两个链表合并的测试样例及结果。

```python

# Test case 1

l1 = ListNode(1)

l1.next = ListNode(2)

l1.next.next = ListNode(4)

l2 = ListNode(1)

l2.next = ListNode(3)

l2.next.next = ListNode(4)

result = mergeTwoListsRecursive(l1, l2)

# Expected output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

# Test case 2

l1 = ListNode(1)

l1.next = ListNode(2)

l1.next.next = ListNode(4)

l2 = None

result = mergeTwoListsIterative(l1, l2)

# Expected output: 1 -> 2 -> 4

```

5.总结：

合并两个链表成为一个链表是一种常见的操作，本文介绍了使用递归和迭代两种算法思路来解决这个问题，并给出了具体的实现代码和测试样例。通过学习和理解这两种算法，我们可以在实际问题中灵活地应用链表操作。