地址 https://leetcode-cn.com/problems/merge-two-sorted-lists/
目描述
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
样例
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
算法1
重点在于不使用额外空间
那么就逐个比较两个链表当前值
1 如果链表1节点值小于链表2节点值 就保留该值 链表1当前检查索引指向下一个链表节点
2 如果链表1节点值大于链表2节点值 交换两链表值后，链表1当前检查索引指向下一个链表节点。同时要保证链表2的升序
1 class Solution { 2 public: 3 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 4 ListNode* head1 = l1; 5 ListNode* head2 = l2; 6 while (l1 != NULL && l2 != NULL) { 7 if (l1->val > l2->val) { 8 swap(l1->val, l2->val); 9 while (l2 != NULL && l2->next != NULL && l2->val > l2->next->val) { 10 swap(l2->val, l2->next->val); 11 l2 = l2->next; 12 } 13 l2 = head2; 14 if (l1->next != NULL) 15 l1 = l1->next; 16 else 17 break; 18 } 19 else { 20 if (l1->next != NULL) 21 l1 = l1->next; 22 else 23 break; 24 } 25 } 26 if(l1 != NULL){ 27 while (l1->next != NULL) { 28 l1 = l1->next; 29 } 30 l1->next = head2; 31 } 32 else { 33 return head2; 34 } 35 36 return head1; 37 } 38 39 };
算法2
投机取巧办法 转化成数组后 再转回链表
C++ 代码
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 12 if(l1==NULL) return l2; 13 if(l2 == NULL) return l1; 14 vector<int> v; 15 ListNode* p = l1; 16 while(p!=NULL){ 17 v.push_back(p->val); 18 p = p->next; 19 } 20 p = l2; 21 while(p!=NULL){ 22 v.push_back(p->val); 23 p = p->next; 24 } 25 sort(v.begin(),v.end()); 26 p =l1; int idx = 0; 27 while(p != NULL){ 28 p->val = v[idx]; 29 idx++; 30 if(p->next == NULL) break; 31 p=p->next; 32 } 33 if(p != NULL) 34 p->next = l2; 35 p =l2; 36 while(p != NULL){ 37 p->val = v[idx]; 38 idx++; 39 if(p->next == NULL) break; 40 p=p->next; 41 } 42 43 return l1; 44 } 45 };
