LeetCode 21. 合并两个有序链表

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！

博主目前仅在ImapBox中写博客，唯一博客更新的地址为：亓官劼的博客

题目

难度 简单

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 

题解一：递归

  这题之前已经写过K个有序链表的合并了，2个就很简单了。我们可以使用递归的写法来进行一个合并的操作，详细的题解代码为：

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == nullptr) { return l2; } else if (l2 == nullptr) { return l1; } else if (l1->val < l2->val) {             l1->next = mergeTwoLists(l1->next, l2); return l1; } else {             l2->next = mergeTwoLists(l1, l2->next); return l2; } } }; 

题解二：迭代

  我们也可以将上面的递归解法修改为迭代解法，我们使用一个ListNode *ans记录答案，使用ListNode *position来进行一个移动，完整的题解代码为：

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {         ListNode *ans = new ListNode(-1);         ListNode *position = ans; while(l1 != nullptr && l2 != nullptr){ if(l1->val < l2->val){                 position->next = l1;                 l1 = l1->next; }else{                 position->next = l2;                 l2 = l2->next; }             position = position->next; }         position->next = l1 == nullptr ? l2 : l1; return ans->next; } }; 

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！

博主目前仅在ImapBox中写博客，唯一博客更新的地址为：亓官劼的博客