21. 合并两个有序链表(三种思路:C实现)
·
题目
题目链接:21. 合并两个有序链表
思路1–无哨兵位迭代方式(尾插)
合并两个链表和合并两个数组的最简单思路都一样的,都是从两个表中比较元素,谁小就放到新的表中;
- 定义newhead = NULL,tail = NULL; newhead 是新链表的头,tail是新链表的尾部;
- 比较l1->val 和 l2->val ,谁小就谁插入newhead的尾巴tail->next中;
- 注意第一次插入的时候,头插的逻辑要单独处理,因为tail == NULL,无法使用tail->next;
- 其次还要注意:l1和l2比较到尾时候,谁先结束到尾,还没到尾的,直接把剩下的链表插入到newhead链表中,即tail->next;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
假如哪个链表为NULL,就返回另一个链表的头结点即可!
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
struct ListNode* newhead = NULL;
struct ListNode* tail = NULL;
while(l1 && l2){
if(l1->val < l2->val){
//第一次尾插的是头结点的话,那么要单独处理
if(newhead == NULL){
newhead = tail = l1;
}
else{ //尾插不是头结点
tail->next = l1;
tail = tail->next;
}
//迭代l1继续往前走
l1 = l1->next;
}
else{ //l2比较小
//第一次尾插的是头结点的话,那么要单独处理
if(newhead == NULL){
newhead = tail = l2;
}
else{ //尾插不是头结点
tail->next = l2;
tail = tail->next;
}
//迭代l2继续往前走
l2 = l2->next;
}
}
//退出循环后,单独判断谁先结束,还没结束的链表直接赋值到tail->next;
if(l1){
tail->next = l1;
}
if(l2){
tail->next = l2;
}
return newhead;
}
思路2–有哨兵位的迭代
有哨兵位就很好处理了,因为对于头结点来说,就不用多一份代码逻辑单独处理它了,有了哨兵位,处理尾插的逻辑就和头插一模一样,不用担心第一次插入的值是否为头部;
注意的是:返回时候要返回哨兵结点的next;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tail = newhead;
while(l1 && l2){
if(l1->val < l2->val){
tail ->next = l1;
l1 = l1->next;
tail = tail->next;
}
else
{
tail->next = l2;
l2 = l2->next;
tail = tail->next;
}
}
//退出循环后,单独判断谁先结束,还没结束的链表直接赋值到tail->next;
if(l1){
tail->next = l1;
}
if(l2){
tail->next = l2;
}
return newhead->next;
}
思路3–递归
链表有天然的递归结构:这道题合并两个有序的链表也可以用递归;
- 比较两个链表l1->val 和 l2->val :谁小就递归谁的next;
- 假如 l1->val < l2->val:,那么递归合并l1->next 和 l2,返回 l1 即可;
- 否则递归l2->next和l1,返回l2即可!
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct 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(l1,l2->next);
return l2;
}
}
更多推荐
已为社区贡献2条内容
所有评论(0)