首页 > 代码库 > 算法题——合并两条有序的链表
算法题——合并两条有序的链表
题目：给定两个已排序的链表，返回合并后的链表。
思路：将链表L2的每个结点插入到链表L1中，时间复杂度为O(m+n)，m、n分别为两条链表的长度。
代码：
1 struct ListNode 2 { 3 int value; 4 ListNode *next; 5 ListNode(int v): value(v), next(NULL) 6 { 7 } 8 }; 9 10 ListNode *mergeSortedList(ListNode *L1, ListNode *L2)11 {12 ListNode dummy(-1), *p1 = &dummy, *p2 = L2; //L1的辅助头结点dummy，因为可能在头部插入13 dummy.next = L1;14 while(p1->next != NULL && p2 != NULL) //停止条件，也包括了判断两个链表是否为空15 {16 if(p1->next->value >= p2->value)17 {18 L2 = p2->next;19 p2->next = p1->next;20 p1->next = p2;21 p1 = p2;22 p2 = L2;23 }24 else25 {26 p1 = p1->next;27 }28 }29 if(p1->next == NULL) //L2可能还有未处理的结点，直接加在L1尾部即可30 {31 p1->next = p2;32 }33 34 return dummy.next;35 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。