首页 > 代码库 > 【leetcode】Merge Two Sorted Lists
【leetcode】Merge Two Sorted Lists
Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
每次找到两个链表中小的一个，把他连接在后面，直到连接完成
思路1：利用递归方法解：递归思路：
if(l1->val<=l2->val)
{
head=l1;
head->next=mergeTwoLists(l1->next,l2);
}
else
{
head=l2;
head->next=mergeTwoLists(l1,l2->next);
}
1 class Solution { 2 public: 3 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { 4 5 if(l1==NULL) 6 { 7 return l2; 8 } 9 10 if(l2==NULL)11 {12 return l1;13 }14 15 ListNode *head;16 17 if(l1->val<=l2->val)18 {19 head=l1;20 head->next=mergeTwoLists(l1->next,l2);21 }22 else23 {24 head=l2;25 head->next=mergeTwoLists(l1,l2->next);26 }27 28 return head;29 30 }31 };
非递归解法：
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 13 if(l1==NULL)14 {15 return l2;16 }17 18 if(l2==NULL)19 {20 return l1;21 }22 23 ListNode *head=new ListNode(0);24 ListNode *pre=head;25 26 while(l1!=NULL||l2!=NULL)27 {28 if(l1==NULL)29 {30 head->next=l2;31 l2=l2->next;32 head=head->next;33 continue;34 }35 36 if(l2==NULL)37 {38 head->next=l1;39 l1=l1->next;40 head=head->next;41 continue;42 }43 44 if(l1->val<=l2->val)45 {46 head->next=l1;47 l1=l1->next;48 head=head->next;49 }50 else51 {52 head->next=l2;53 l2=l2->next;54 head=head->next;55 }56 }57 58 ListNode *ret=pre->next;59 delete pre;60 return pre->next;61 62 }63 };
【leetcode】Merge Two Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。