7-2 两个有序链表序列的合并 (20 分)

题目描述

将两个单调递增的链表合并为一个单调不减的链表，例如链表1为1->3->5->7，链表2为2->4->6->8，则合并后的链表应该为1->2->3->4->5->6->7->8，链表节点定义如下：

struct ListNode {
int val;
struct ListNode *next;
};

函数定义

struct ListNode* merge(struct ListNode* pHead1, struct ListNode* pHead2);

输入参数

- pHead1: 链表1的头结点
- pHead2: 链表2的头结点

输出参数

- 返回合并后的链表头结点

样例

输入:

链表1: 1->3->5->7
链表2: 2->4->6->8

输出:

合并后的链表: 1->2->3->4->5->6->7->8

解题思路

这道题可以用递归或者迭代两种方法来解决。

递归方法

递归方法的思路是，比较两个链表的头结点，将较小的头结点作为合并后链表的头结点，然后递归地合并剩余的链表。

迭代方法

迭代方法的思路是，用一个指针p指向合并后链表的尾结点，然后比较两个链表的头结点，将较小的头结点接到p的后面，然后将p指向新的尾结点，继续比较两个链表的头结点，直到其中一个链表为空，然后将另一个链表接到合并后链表的尾部。

参考代码

递归方法

struct ListNode* merge(struct ListNode* pHead1, struct 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;
}
}

迭代方法

struct ListNode* merge(struct ListNode* pHead1, struct ListNode* pHead2) {
if (pHead1 == NULL) {
return pHead2;
}
if (pHead2 == NULL) {
return pHead1;
}
struct ListNode* p = NULL;
if (pHead1->val < pHead2->val) {
p = pHead1;
pHead1 = pHead1->next;
} else {
p = pHead2;
pHead2 = pHead2->next;
}
struct ListNode* head = p;
while (pHead1 != NULL && pHead2 != NULL) {
if (pHead1->val < pHead2->val) {
p->next = pHead1;
pHead1 = pHead1->next;
} else {
p->next = pHead2;
pHead2 = pHead2->next;
}
p = p->next;
}
if (pHead1 != NULL) {
p->next = pHead1;
}
if (pHead2 != NULL) {
p->next = pHead2;
}
return head;
}