将两个单链表合并为一个单链表exp2-7.cpp。令L1=（x1,x2,x3……,xn ），L2=（y1,y2,y3，……,yn），设计一个算法合并L1、L2，结果放在线性表L3中， L3=（x1,y1,x2,y2,x3,y3……，xn,yn）

### C++ 实现两个单链表交错合并为新链表 以下是基于题目需求编写的 C++ 示例代码，用于将两个单链表 `L1` 和 `L2` 的节点按照交错顺序合并到新的线性表 `L3` 中。如果其中一个链表先结束，则剩余部分直接连接至 `L3`。 ```cpp #include <iostream> using namespace std; // 定义链表节点结构体 struct ListNode { int data; ListNode* next; ListNode(int val) : data(val), next(nullptr) {} }; // 创建链表函数 ListNode* createList(const int arr[], int n) { if (n == 0) return nullptr; ListNode *head = new ListNode(arr[0]); ListNode *current = head; for (int i = 1; i < n; ++i) { current->next = new ListNode(arr[i]); current = current->next; } return head; } // 打印链表函数 void printList(ListNode* head) { while (head != nullptr) { cout << head->data << " "; head = head->next; } cout << endl; } // 交错合并两个链表 ListNode* mergeAlternately(ListNode* L1, ListNode* L2) { ListNode dummy(0); // 虚拟头结点 ListNode* tail = &dummy; while (L1 && L2) { // 当两者均不为空时 tail->next = L1; // 将 L1 的当前节点加入结果链表 L1 = L1->next; tail = tail->next; tail->next = L2; // 将 L2 的当前节点加入结果链表 L2 = L2->next; tail = tail->next; } // 如果某个链表还有剩余节点，直接接上 if (L1) tail->next = L1; if (L2) tail->next = L2; return dummy.next; // 返回实际的头部 } int main() { const int arr1[] = {1, 3, 5}; const int arr2[] = {2, 4, 6, 8, 10}; ListNode* L1 = createList(arr1, sizeof(arr1)/sizeof(arr1[0])); ListNode* L2 = createList(arr2, sizeof(arr2)/sizeof(arr2[0])); cout << "原始链表 L1: "; printList(L1); cout << "原始链表 L2: "; printList(L2); ListNode* L3 = mergeAlternately(L1, L2); cout << "合并后的链表 L3: "; printList(L3); return 0; } ``` #### 关键说明 上述程序实现了如下功能： - 使用虚拟头结点简化边界条件处理[^2]。 - 遍历两个输入链表 `L1` 和 `L2`，依次将其节点按交错方式添加到目标链表 `L3` 中。 - 若某一链表提前耗尽，则直接将另一链表的剩余部分附加到 `L3` 上[^3]。 此方法的时间复杂度为 O(n+m)，其中 n 和 m 分别表示两链表长度；空间复杂度为 O(1)，因为除了返回的新链表外未使用额外存储资源[^4]。