Leedcode-剑指 Offer 25. 合并两个排序的链表----C++实现

本文主要是介绍Leedcode-剑指 Offer 25. 合并两个排序的链表----C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目的

旨在记录在Leedcode网上刷题的过程，记录心得。

题目

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：

0 <= 链表长度 <= 1000

思路：

思路1：将2个链表的数据取出来，排好序，重新创建新的链表，返回

这个思路与此前的文章Leedcode编程题23： 合并K个排序链表----C++实现类似，代码略。

思路2：使用伪头结点

时间复杂度：o(m+n),m、n分别是l1和l2的长度

空间复杂度：o(1)

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:
/*
思路2：使用伪头结点
时间复杂度：o(m+n),m、n分别是l1和l2的长度
空间复杂度：o(1)
*/ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode dum = ListNode(0);ListNode* cur = &dum;while(l1 && l2) {if(l1->val < l2->val) {cur->next = l1;l1 = l1->next;}else {cur->next = l2;l2 = l2->next;}cur = cur->next;}cur->next = l1? l1 : l2;return dum.next;}
};

效果：

 

 

这篇关于Leedcode-剑指 Offer 25. 合并两个排序的链表----C++实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---