输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
两种思路：递归和非递归
先说递归吧，
// 先判断两个链表指针是否为空，如果链表一为空，则返回第二个
// 如果链表二为空，则返回第一个.如果都是空，合并后也是空
//两个链表都是有序的，遍历链表，判断当前指针，那个链表值小，就把合并的链表指向它
//然后递归
class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(pHead1 == nullptr ) return pHead2; if(pHead2 == nullptr) return pHead1; ListNode *pNew = nullptr; if(pHead1->val < pHead2->val) { pNew = pHead1; pNew->next = Merge(pHead1->next, pHead2); } else { pNew = pHead2; pNew->next = Merge(pHead1, pHead2->next); } return pNew; } };
非递归：
思路：
申请一个head节点，任意保存一个值，用pNew指向它，然后进行迭代，最后返回head->next
// 利用一个辅助空间head，pNew指向它，返回它的后一个节点 class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(pHead1 == nullptr ) return pHead2; if(pHead2 == nullptr) return pHead1; // 存放中间变量 ListNode *head = new ListNode(1); ListNode *pNew = head; while(pHead1!=nullptr && pHead2 != nullptr) { if (pHead1->val < pHead2->val) { pNew->next = pHead1; pHead1 = pHead1->next; } else { pNew->next = pHead2; pHead2 = pHead2->next; } pNew = pNew->next; } if (pHead1 != nullptr) pNew->next = pHead1; if(pHead2 != nullptr) pNew->next = pHead2; return head->next; } };
原文：https://www.cnblogs.com/xiaokang01/p/12493872.html