Jzoffer -JZ16 合并两个排序的链表

合并两个排序的链表

https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&&tqId=11169&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

C++
题目给了两个升序的链表,需要进行合并,要求保证合并后的链表依然成单调不减。
这里其实需要进行每个节点比较判断, 可以理解为一个改进后的节点插入。
这里给出最直接的思路:
图片说明
代码如下:

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
        //特殊情况处理
        if(pHead1 == nullptr) return pHead2;
        if(pHead2 == nullptr) return pHead1;
        //------二者皆不为空
        //声明变量,没有问题
        ListNode* head = nullptr;
        ListNode* tial = nullptr;
        //构建第一关系
        if(pHead1->val <= pHead2->val){
            head = pHead1;
            pHead1 = pHead1->next;
        }else{
            head = pHead2;
            pHead2 = pHead2->next;
        }
        tial = head;
        //对头指针合法性判断
        while(pHead1 != nullptr && pHead2 != nullptr){
            if(pHead1->val <= pHead2->val){
                tial->next = pHead1;
                pHead1 = pHead1->next;
            }else{
                tial->next = pHead2;
                pHead2 = pHead2->next;
            }
            tial = tial->next;
        }
        //对跳出判断
        if(pHead1 != nullptr){//2结束 1 未结束, 直接补1
            tial->next = pHead1;
        }else if(pHead2!=nullptr){//1结束 2未结束, 直接补2
            tial->next = pHead2;
        }else{// 1 2 均结束,补nullptr
                tial->next=nullptr;
        }
        return head;
    }
};

这里记录一下自己出错的一版代码,并给出问题分析:

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // bundary 
        if (!pHead1 && !pHead2){
            return nullptr;
        }else if(!pHead1){
            return pHead2;
        }else if(!pHead2){
            return pHead1;
        }
        // creat 
        ListNode* p1=pHead1;
        ListNode* p1_next = pHead1->next;
        ListNode* p2 = pHead2;
        ListNode* p2_next = pHead2;
        ListNode* head;
        ListNode* current = head;
        while(p1!=nullptr && p2 !=nullptr){
            if(p1->val > p2->val){
                current->next = p1;
                p1=p1_next;
                p1_next=p1->next;
            }else{
                current->next = p2;
                p2 = p2_next;
                p2_next = p2->next;
            }
            current = current->next;
        }
        if(p1!=nullptr){
            current->next = p1;
        }else if(p2!=nullptr){
            current->next = p2;
        }
        return head;
    }

1、首先边界判断有点冗余, 但是没有逻辑错误。
2、每个链表的哨兵(头结点)更新有点冗余, 但是依然没有逻辑错误。
3、单单从while循环看, 除过冗余的变量p_next之外, 更新插入的逻辑也没有问题,但是这里head一直指向nullptr, 它的next才是真正新链表的头结点, current一直在维护这个,但是没有被记录下来。
最关键这里第一次current在指向nullptr的情况下对next赋值, 这里直接报错, 一直没查找出来, 以后要注意

全部评论

相关推荐

流岚噗噗:肯定直接说第一啊,网上的身份都是自己给的好吧
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务