链接

---

牛客OJ&＃xff1a;合并两个排序的链表

九度OJ&＃xff1a;http://ac.jobdu.com/problem.php?pid&＃61;1519

GitHub代码&＃xff1a; 017-合并两个排序的链表

CSDN题解&＃xff1a;剑指Offer–017-合并两个排序的链表

牛客OJ	九度OJ	CSDN题解	GitHub代码
合并两个排序的链表	1519-合并两个排序的链表	剑指Offer–017-合并两个排序的链表	017-合并两个排序的链表

您也可以选择回到目录-剑指Offer–题集目录索引

其实这道题跟LeetCode上一道题是一样的

LeetCodet题解–21. Merge Two Sorted Lists&＃xff08;合并两个排序好的链表&＃xff09;

当然他还有很多变种&＃xff0c;比如说两个链表扩展成为K个的时候

LeetCodet题解–23. Merge k Sorted Lists&＃xff08;合并K个已排序的链表&＃xff09;

题意

---

题目描述

输入两个单调递增的链表&＃xff0c;输出两个链表合成后的链表&＃xff0c;当然我们需要合成后的链表满足单调不减规则。

样例输入

1 3 5 7 9
2 4

样例输出

1 2 3 4 5 7 9

常规写法

---

思路很简单&＃xff0c;用两个指针同步遍历两个链表&＃xff0c;每次找到小的那个插入到新的链表中

#include using namespace std;// 调试开关
#define __tmain main#ifdef __tmain#define debug cout#else#define debug 0 && cout#endif // __tmain#ifdef __tmain
struct ListNode
{
public :int val;struct ListNode *next;
// ListNode(int x)
// :val(x), next(NULL)
// {
// }
};#endif // __tmainclass Solution
{
public:ListNode* Merge(ListNode *pLeft, ListNode *pRight){if(pLeft &＃61;&＃61; NULL){debug <<"left list is NULL" <return pRight;}else if(pRight &＃61;&＃61; NULL){debug <<"right list is NULL" <return pLeft;}ListNode *left &＃61; pLeft;ListNode *right &＃61; pRight;// 先生成头结点ListNode *head &＃61; NULL;if(left->val val){head &＃61; left;left &＃61; left->next;debug "in list" <else{head &＃61; right;right &＃61; right->next;debug "in list" <// 遍历两个链表ListNode *curr &＃61; head;while(left !&＃61; NULL && right !&＃61; NULL){// 每次找到一个小的加入新的链表debug <<"left &＃61; " <val <<", right &＃61; " <val <if(left->val val){debug <val <<"in list" <next &＃61; left;curr &＃61; curr->next;left &＃61; left->next;}else{debug <val <<"in list" <next &＃61; right;curr &＃61; curr->next;right &＃61; right->next;}}// 处理较长链表的剩余部分if(left !&＃61; NULL){curr->next &＃61; left;}else{curr->next &＃61; right;}return head;}
};int __tmain( )
{ListNode left, right[3];left.val &＃61; 5;left.next &＃61; NULL;right[0].val &＃61; 1;right[0].next &＃61; &right[1];right[1].val &＃61; 2;right[1].next &＃61; &right[2];right[2].val &＃61; 4;right[2].next &＃61; NULL;Solution solu;ListNode *head &＃61; solu.Merge(&left, right);while(head !&＃61; NULL){cout next;}return 0;
}


递归实现

---

其实思路一样&＃xff0c;只是由于每次添加节点&＃xff0c;都是机械性地重复工作&＃xff0c;因此可以用递归来实现


class Solution
{
public:ListNode* Merge(ListNode *pLeft, ListNode *pRight){if(pLeft &＃61;&＃61; NULL){debug <<"left list is NULL" <return pRight;}else if(pRight &＃61;&＃61; NULL){debug <<"right list is NULL" <return pLeft;}ListNode *head &＃61; NULL;if(pLeft->val val){head &＃61; pLeft;head->next &＃61; Merge(pLeft->next, pRight);}else{head &＃61; pRight;head->next &＃61; Merge(pLeft, pRight->next);}return head;}
};