首页 > 代码库 > [LeetCode]21.Merge Two Sorted Lists
[LeetCode]21.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.
【分析】
无
【代码】
/********************************* * 日期:2015-01-06 * 作者:SJF0115 * 题目: 21.Merge Two Sorted Lists * 来源:https://oj.leetcode.com/problems/merge-two-sorted-lists/ * 结果:AC * 来源:LeetCode * 博客: **********************************/ #include <iostream> using namespace std; struct ListNode{ int val; ListNode *next; ListNode(int x):val(x),next(NULL){} }; class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode *head = new ListNode(-1); ListNode *p1 = l1,*p2 = l2,*cur = head; while(p1 != NULL && p2 != NULL){ // 取两个链表头的较小元素 if(p1->val < p2->val){ cur->next = p1; p1 = p1->next; }//if else{ cur->next = p2; p2 = p2->next; }//else cur = cur->next; }//while // 如果链表1没有遍历完 while(p1){ cur->next = p1; p1 = p1->next; cur = cur->next; }//while // 如果链表2没有遍历完 while(p2){ cur->next = p2; p2 = p2->next; cur = cur->next; }//while cur->next = NULL; return head->next; } }; int main() { Solution solution; int A[] = {1,2,4,7,9}; int B[] = {3,5,8,10,11,12}; // 链表1 ListNode *head1 = new ListNode(A[0]); ListNode *p1 = head1; for(int i = 1;i < 5;i++){ ListNode *node = new ListNode(A[i]); p1->next = node; p1 = node; }//for // 链表2 ListNode *head2 = new ListNode(B[0]); ListNode *p2 = head2; for(int i = 1;i < 6;i++){ ListNode *node = new ListNode(B[i]); p2->next = node; p2 = node; }//for ListNode *head = solution.mergeTwoLists(head1,head2); // 输出 ListNode *p = head; while(p){ cout<<p->val<<" "; p = p->next; }//while cout<<endl; }
【代码二】
递归实现
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; } else { l2->next = mergeTwoLists(l2->next, l1); return l2; } } };
[LeetCode]21.Merge Two Sorted Lists
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。