《五月集训》第二十九日——分而治之

这是五月集训的第二十九日，今日的训练内容是 分而治之

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

这题我使用的思路是使用递归，最开始的思路是重新创建一个新的函数使用递归将前两个传入的链表都填入第三个链表中，但是这样出现了空指针的bug，找了一阵子没有想明白问题出在哪里，直接换思路吧。

仍然是递归，这次直接使用函数本身进行递归好了。首先来考虑一下递归的出口，不论 list1 和 list2哪一方链表结束了，那接下来就直接把没结束的链表填到当前链表的后面也就可以了。

顺着这个思路，那假如两个链表都没结束，那就对当前的两个链表指针指向的结点的值域进行比较，拿 list1->val 比较大的情况进行说明。 list1->val 既然比较大的话，那就说明 list2的结点就要填在当前的位置了，所以我们就可以拿 list2 作为返回的链表，接下来的操作就直接对它进行就可以了，因为链表的表头就肯定是指针现在指向的结点，所以现在开始填充下一项吧，下一项要进行的也是一样的操作，于是我们就可以使用 list2->next=mergeTwoLists(list1,list2->next);进行递归，对最终返回链表的每一项都进行相同的操作，填充完之后直接返回头指针就可以了，因为每一次递归都是对没有操作过的结点进行操作。

值得一说的是，这个思路就是归并排序的链表实现方法。只不过这是进行到了最后一步的归并。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1==NULL) return list2;
    if(list2==NULL) return list1;
    if(list1->val>list2->val){
       list2->next=mergeTwoLists(list1,list2->next);
       return list2;
    }else{
        list1->next=mergeTwoLists(list1->next,list2);
        return list1;
    }
}

1985. 找出数组中的第 K 大整数

给你一个字符串数组 nums 和一个整数 k 。nums 中的每个字符串都表示一个不含前导零的整数。

返回 nums 中表示第 k 大整数的字符串。

注意：重复的数字在统计时会视为不同元素考虑。例如，如果 nums 是 [“1”,“2”,“2”]，那么 “2” 是最大的整数，“2” 是第二大的整数，“1” 是第三大的整数。

直接使用qsort()排序即可。

int cmp(const void*a,const void*b){
    char *aa = *(char**)a;
    char *bb = *(char**)b;
    int la = strlen(aa);
    int lb = strlen(bb);
    if (la == lb) {
        return strcmp(bb, aa);
    }
    return lb - la;
}
char * kthLargestNumber(char ** nums, int numsSize, int k){
    qsort(nums, numsSize, sizeof(nums[0]), cmp);
    return nums[k - 1];
}

558. 四叉树交集

932. 漂亮数组