题意为将两个已经排好序的链表合并为一个新的有序链表 可以用递归和非递归两种方法解决问题：
（1）非递归
首先需要创建一个新的链表，然后依次遍历两个链表，并将两个数组中较小的元素依次插入新链表中。 值得注意的是，若一个链表为空或已经遍历完全，则将另一个链表插入即可
class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *head = new ListNode(-1); ListNode *p1 = l1; ListNode *p2 = l2; ListNode *curNode = head; while(p1 && p2) { if( p1->val < p2->val ) { curNode->next = p1; curNode = curNode->next; p1 = p1->next; } else if(p2->val < p1->val ) { curNode->next = p2; curNode = curNode->next; p2 = p2->next; } else { curNode->next = p1; curNode = curNode->next; p1 = p1->next; curNode->next = p2; curNode = curNode->next; p2 = p2->next; } } if(p1) { curNode->next = p1; } if(p2) { curNode->next = p2; } return head->next; }};（2）递归
考虑，若链表 l1 为空，则返回 l2 链表；若 l2 链表为空，则返回 l1 链表 若两链表均非空，则比较链表 l1 和 l2 的第一个元素，若 l1 较小，则继续比较 l1->next 和 l2 的第一个元素大小，并返回 l1
class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == NULL) { return l2; } if(l2 == NULL) { return l1; } if(l1->val < l2->val) { l1->next = mergeTwoLists(l1->next,l2); return l1; } if(l2->val <= l1->val) { l2->next = mergeTwoLists(l1,l2->next); return l2; } }};新闻热点
疑难解答
