题解 | #二分查找-I#

核心思想

• 三刷了，居然一些关键条件还是忽略

1. 判空
2. 定义新节点， 免除额外求得头指针
3. 判断两个链表都不能为空 - while(pHead1 != NULL && pHead2 != NULL)
4. 比较的时候，需要注意相等的情况， 相等部分可以优化

• 三刷答案

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    // 判空
    if(pHead1 == NULL)
    {
        return pHead2;
    }
    else if (pHead2 == NULL)
    {
        return pHead1;
    }    
    
    // 定义新节点，就不用做预先比较了
    struct ListNode newHead = {};
    struct ListNode * move = &newHead;
    move->next = NULL;
    
    // 遍历两个比较链表，任意到尾结点，就退出
    while(pHead1 != NULL && pHead2 != NULL)
    {
        if(pHead1->val < pHead2->val)
        {
            move->next = pHead1;
            move = move->next;
            pHead1 = pHead1->next;
            move->next = NULL;
        }
        else if(pHead2->val < pHead1->val)
        {
            move->next = pHead2;
            move = move->next;
            pHead2 = pHead2->next;
            move->next = NULL;
        }
        else
        {
            move->next = pHead2;
            move = move->next;
            pHead2 = pHead2->next;
            move->next = NULL;
            
            move->next = pHead1;
            move = move->next;
            pHead1 = pHead1->next;
            move->next = NULL;
        }
    }
        
    // 若有相对较长的，就挂到新链表的尾结点上
    if(pHead1 != NULL)
    {
        move->next = pHead1;
    }
    if(pHead2 != NULL)
    {
        move->next = pHead2;
    }
    
    return (&newHead)->next;
}

• 2刷答案

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    // 分别判断是否为空
    if(pHead1 == NULL)
    {
        return pHead2;
    }
        
    if(pHead2 == NULL)
    {
        return pHead1;
    }
    
    // 排序,此刻两个不为空的链表，以pHead1为基准
    struct ListNode * newHead=NULL;
    // curr是关键，游离在两个链表之间
    struct ListNode * curr=NULL;
    
    if(pHead1->val > pHead2->val)
    {
        newHead=pHead2;
        curr=pHead2;
        pHead2=pHead2->next;
    }
    else
    {
        newHead=pHead1;
        curr=pHead1;
        pHead1=pHead1->next;        
    }

    // 遍历两个node节点，挨个节点判断纳入新节点
    // 注意摘节点的步骤
    while(pHead1 != NULL && pHead2 != NULL )
    {
        if(pHead1->val < pHead2->val)
        {
            // 摘取小的结点
            curr->next = pHead1;
            curr=pHead1;
            pHead1=pHead1->next;
        }
        // 这块万可不能用if (pHead1->val > pHead2->val)
        else
        {
            curr->next = pHead2;
            curr=pHead2;
            pHead2=pHead2->next;
        }
    }
    
    // 剩余谁是null
    if(pHead1 == NULL)
    {
        curr->next = pHead2;
    }
    else
    {
        curr->next = pHead1;
    }
    
    return newHead;
}