我是靠谱客的博主 无聊皮皮虾,这篇文章主要介绍合并两个有序列表,现在分享给大家,希望可以做个参考。

本来很简单一题,很久没写算法题了居然在细节上纠结了我好久,唉~
这种简单题就应该用简单的思路来做…在这也提醒各位,有的题真的只是看起来容易,真的写起来又会有好多乱七八糟的问题了。

闲话少说,上题吧,这是leetcode的第21题,各位可以去网站上面刷刷,经过那个测试才知道你的代码会不会有你没发现的问题。
在这里插入图片描述

分析:
首先,题目所给的函数如下,返回是一个指针,如果我在函数内部动态malloc一个链表,那么必然导致在出了函数之后那块地址被释放了,所以返回值只能从输入的参数下手。我这里选择的是l1,即将l2中的元素依次插入l1中。

复制代码
1
2
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {}

再来看题目,很显然输入的是一个不带头结点的单链表,这用起来就很麻烦,毕竟我里面要频繁地进行插入操作,而插入操作要求对链表的->next节点进行操作,因为每当l2指向的元素比l1指向的元素小时,我要把l2指向的元素插入到l1所指的元素的前面的,如果不带头结点那就操作起来太麻烦了,因此我们可以自己定义头结点,我的程序里为head1和head2

有头结点还不行,要考虑一个情况:

复制代码
1
2
3
l1: [2] l2: [1]

按照上面的思路,l2已经能够全部正常插入了,但是这种情况下,l1指针要如何保持指向第一个元素呢?因此我在代码里添加了如下代码:

复制代码
1
2
if(head1->next->next == l1) l1 = head1->next;

最后要考虑l1为空的问题,如果l1为空那么直接返回l2就好了。


以下为我的代码:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(!l1) return l2; ListNode* head1 = (ListNode*)malloc(sizeof(ListNode)); ListNode* head2 = (ListNode*)malloc(sizeof(ListNode)); head1->next = l1; head2->next = l2; while(head1->next && head2->next) { if(head1->next->val > head2->next->val) { ListNode* temp2 = head2->next->next; head2->next->next = head1->next; head1->next = head2->next; head2->next = temp2; if(head1->next->next == l1) l1 = head1->next; } head1 = head1->next; } if(head2->next) { while(head1->next) head1=head1->next; head1->next = head2->next; } return l1; } };

好嘛,我觉得代码写的还是挺菜的…
在这里插入图片描述

最后

以上就是无聊皮皮虾最近收集整理的关于合并两个有序列表的全部内容,更多相关合并两个有序列表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(83)

评论列表共有 0 条评论

立即
投稿
返回
顶部