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;

        
    }
};

总结:
以后还是要先做再写笔记,不能喧宾夺主,这次又用了很长时间,不过有收获总归是好的,继续加油!