在C++编程中，合并两个已经排序的链表是一个常见的数据结构问题，它涉及到链表的基本操作和比较。本文将介绍两种不同的方法来解决这个问题，一种是基于迭代的方法（方法一），另一种是基于递归的方法（方法二）。
我们需要理解链表的基本结构。在C++中，链表通常通过定义一个结构体或类来实现，包含一个整数值（val）和一个指向下一个节点的指针（next）。例如：
```cpp
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
```
### 方法一：迭代法
这个方法使用两个指针，`newList`和`newListRear`，分别表示新的合并后链表的头节点和尾节点。处理特殊情况，即其中一个链表为空，那么返回另一个非空链表即可。接着，比较两个链表的头节点值，将较小的节点添加到新链表中，并更新相应的指针。然后，循环遍历两个链表，直到其中一个为空，此时将另一个链表的剩余部分接到新链表的尾部。最后返回新链表的头节点。
```cpp
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* newList = NULL;
ListNode* newListRear = NULL;
if (pHead1 == NULL) return pHead2;
if (pHead2 == NULL) return pHead1;
if (pHead1->val <= pHead2->val) {
newList = pHead1;
newListRear = pHead1;
pHead1 = pHead1->next;
} else {
newList = pHead2;
newListRear = pHead2;
pHead2 = pHead2->next;
}
while (pHead1 != NULL && pHead2 != NULL) {
if (pHead1->val <= pHead2->val) {
newListRear->next = pHead1;
newListRear = pHead1;
pHead1 = pHead1->next;
} else {
newListRear->next = pHead2;
newListRear = pHead2;
pHead2 = pHead2->next;
}
}
if (pHead1 == NULL) {
newListRear->next = pHead2;
} else {
newListRear->next = pHead1;
}
return newList;
}
```
### 方法二：递归法
递归方法利用了函数自身调用的特性。同样，当一个链表为空时，返回另一个链表。然后，比较两个链表的头节点值，如果`pHead1`的值小于等于`pHead2`，则将`pHead1`的下一个节点与`pHead2`进行合并，并将结果作为`pHead1->next`，返回`pHead1`作为新链表的头节点。反之，将`pHead2`的下一个节点与`pHead1`进行合并，并将结果作为`pHead2->next`，返回`pHead2`作为新链表的头节点。
```cpp
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if (pHead1 == NULL) return pHead2;
if (pHead2 == NULL) return pHead1;
if (pHead1->val <= pHead2->val) {
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
} else {
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
}
```
无论是迭代还是递归方法，最终的目标都是创建一个新的链表，其中的节点按值从小到大排列，同时保持原有的链表顺序。这两种方法都能有效地解决问题，但在实际应用中，由于递归方法涉及函数调用开销，可能会比迭代方法更消耗资源，尤其是当链表长度较大时。因此，选择哪种方法取决于具体的需求和性能考虑。
