用了一个比较复杂的方法, 直接讲两个链表的数据取出来,使用vector进行排序, 然后再链接两个链表, 在把数据插回去. 不如递归简单.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *p = l1; ListNode *q = l2; if(p == nullptr && q == nullptr){ return p; } // 将p插入q中 vector<int> v; while(p){ v.push_back(p->val); p = p->next; } while(q){ v.push_back(q->val); q = q->next; } sort(v.begin(), v.end()); if(l1 != nullptr){ p = l1; while(p->next){ p = p->next; } p->next = l2; p = l1; int i=0; while(p){ p->val = v[i]; i++; p = p->next; } return l1; }else{ q = l2; while(q->next){ q = q->next; } q->next = l1; q = l2; int i=0; while(q){ q->val = v[i]; i++; q = q->next; } return l2; } return nullptr; } };
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null){ return l2; } else if(l2 == null){ 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; } } }
递归算法很巧妙, 不用构造零时指针. 及其方便