链表OJ题之——合并有序链表

文章目录

初级题目:

题目链接:leetcode
链表OJ题之——合并有序链表

思路:创建一个新的头指针和两个分别指向链表的指针l1、l2,对两个指针所指向的值进行比较,将小的值的节点给新的头节点。直到第一个指针到达结尾,将另外一个指针指向的剩余内容给到新的链表。
以题目中给的链表为例:
创建好链表
链表OJ题之——合并有序链表
第一步:
链表OJ题之——合并有序链表
第二步:

链表OJ题之——合并有序链表
第三步:

链表OJ题之——合并有序链表
第四步:

链表OJ题之——合并有序链表
第五步:

链表OJ题之——合并有序链表
第六步:

链表OJ题之——合并有序链表
特殊情况考虑:当l1或l2中有一个为空指针时,直接返回另外一个指针就行了


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1==NULL)
    return l2;
    if(l2==NULL)
    return l1;
    struct ListNode*newhead=NULL;
    struct ListNode*cur=NULL;
    while(l1&&l2)
    {
        if(l1->val>l2->val)
        {
            if(newhead==NULL)
            {
                newhead=cur=l2;
                l2=l2->next;
                continue;
            }
            cur->next=l2;
            cur=cur->next;
            l2=l2->next;
        }
        else
        {
            if(newhead==NULL)
            {
                newhead=cur=l1;
                l1=l1->next;
                continue;
            }
            cur->next=l1;
            cur=cur->next;
            l1=l1->next;
        }
    }

    if(l1==NULL)
    cur->next=l2;

    if(l2==NULL)
    cur->next=l1;

    return newhead;

}

进阶题目

题目链接:leetcod
链表OJ题之——合并有序链表
思路: 这道题思路和上一题几乎一样,因为传进来的时一个指针数组,所以我们每次要通过遍历每个链表的头指针的值来找出最小值。将最小值给新的头节点,然后直到最后一个节点到空指针
这题有两个要注意的地方:

  1. 要找到头节点中的最小值,我采用的方法是先找到第一个不为空指针的链表头节点的值,把他赋给min并于剩下的头节点的值进行比较,如果遇到跟小的就替换,但是要注意检查头节点是否为空指针
  2. 要找到循环结束的条件:所有的头节点的指针都是空指针时结束,我这里建立了函数fun2来实现
链表OJ题之——合并有序链表链表OJ题之——合并有序链表
链表OJ题之——合并有序链表链表OJ题之——合并有序链表
链表OJ题之——合并有序链表链表OJ题之——合并有序链表
链表OJ题之——合并有序链表链表OJ题之——合并有序链表
链表OJ题之——合并有序链表链表OJ题之——合并有序链表
int fun2(struct ListNode** lists, int listsSize)
{
    for (int i = 0; i < listsSize; i++)
    {
        if (*(lists + i) != NULL)
            return 1;
    }
    return 0;

}
struct SListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    
    if (lists == NULL)
        return NULL;
    struct ListNode* newhead = NULL;
    struct ListNode* cur = NULL;

    while (fun2(lists, listsSize))
    {
        int min;
        int k = 0;
        for (int i = 0; i < listsSize; i++)
        {
            if (*(lists + i) != NULL)
            {
                min = (*(lists + i))->val;
                k = i;
                break;
            }
        }
        for (int i = 0; i < listsSize; i++)
        {
            if (*(lists + i))
            {
                if ((*(lists + i))->val < min)
                {
                    min = (*(lists + i))->val;
                    k = i;
                }
            }
        }
        if (newhead == NULL)
        {
            cur = newhead = *(lists + k);
            *(lists + k) = (*(lists + k))->next;
            continue;
        }
        (cur)->next = *(lists + k);
        *(lists + k) = (*(lists + k))->next;
        cur = (cur)->next;
    }

    if(cur)
    cur->next = NULL;
    return newhead;
}
上一篇:D-OJ刷题日记:求最小值 题目编号:1121


下一篇:nowcoder-oj【面试高频TOP榜单-入门难度】