leetcode刷题06--排序链表的合并--T21
题目:
image.png
自己思路:
超时了,还是记录一下,哎,自己还是真的菜,要多练才行!
/**
* 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==NULL){
return l2;
}
if(l2==NULL){
return l1;
}
ListNode *head = l1->val>=l2->val?l2:l1;
ListNode *headA = l1;
//对于两个有序的链表可以采用插入排序
while(l2){
while(l1){
//先存头结点
headA = l1->next;
if(headA == NULL){
break;
}
//判断小于的情况
if(l1->val<l2->val){
l1->next = l2;
l1 = headA;
}else if(l1->val>=l2->val){
//判空
if(l2->next == NULL){
l1->next =NULL;
l2->next = l1;
l1 = headA;
continue;
}
if(l1->val<=l2->next->val){
//可以插入
//插入
l1->next = l2->next;
l2->next = l1;
l1 = headA;
}
}else{
//这种情况是大于后面的那个节点,直接跳出循环
break;
}
}
l2 = l2->next;
}
return head;
}
};
PPT思路
image.png
一下就理解了,利用一个临时节点及临时指针,简直一下就做完了,想到我的方法,简直哭泣,算法能力还是太菜了,要多练!
代码(简单好多!):
/**
* 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) {
ListNode tem_head(0);
ListNode *ptr = &tem_head;
while(l1&&l2){
//如果l1小
if(l1->val <= l2->val){
ptr->next = l1;
//l1向后移动一位
l1 = l1->next;
}else{
ptr->next = l2;
//l2向后移动一位
l2 = l2->next;
}
//指向新连接的节点
ptr = ptr->next;
}
//不用考虑tem中有无值得情况,直接将剩余的接上去,都是一样的
if(l1){
//剩下的都是大于tem中的数
ptr->next=l1;
}
if(l2){
//剩下的都是大于tem中的数
ptr->next=l2;
}
return tem_head.next;
}
};
总结:
以后还是要先做再写笔记,不能喧宾夺主,这次又用了很长时间,不过有收获总归是好的,继续加油!
