剑指 Offer 25. 合并两个排序的链表
思路：
当两个链表都不为空时，比较两个链表的头节点哪个更小，将小的节点添加到新的链表中，然后将指向该节点的指针向后移动一位。
实现方式：
1.首先先创建哨兵位节点guard，避免两个链表的头节点谁大谁小的特殊判断；2.接下来分别从两个链表的头节点开始进行判断，分别维护两个指针cur1和cur2（分别指向链表的头节点），让其随着判断大小并添加到新链表中的操作而移动；再维护一个tail指针指向新链表的尾节点，用于链接新添加的节点；3.判断两个链表中cur1和cur2所指向节点大小，将小的添加到新链表中，并让其指针向后移动一位；4.当一个链表走到NULL时，我们就将另外一个链表其余节点全部连接到新的链表中。5.最后返回哨兵位节点的下一个节点。
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
//1.创建哨兵位节点
struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
//2.维护两个指针cur1指向l1 ，cur2指向l2
struct ListNode* cur1 = l1, *cur2 = l2;
//维护一个tail指针指向新链表的尾节点
struct ListNode* tail = guard;
//3.进行比较
while(cur1 != NULL && cur2 != NULL)
{
if(cur1->val < cur2->val)
{
tail->next = cur1;//将cur1添加到新链表中
tail = cur1;//刷新新链表的尾节点
cur1 = cur1->next;//cur1向后移动一位
}
else
{
tail->next = cur2;
tail = cur2;
cur2 = cur2->next;
}
}
//4.当有一个链表走到NULL时
//当cur1为空,cur2就不为空
if(cur2)
tail->next = cur2;
else
tail->next = cur1;
//5.返回哨兵位的下一个节点
return guard->next;
}
23. 合并K个升序链表
做完合并两个排序链表后，我们再来看看这道题，就会显得不那么困难了，但在这之前，我们还需要掌握归并排序，如果二者兼备，那么这道题就能迎刃而解。
思路：
将链表数组中的每2个链表进行合并，n个链表在第一次合并时，会被合并为n/2个，接下来是：n/4，n/8…,直到合并剩下1个链表。
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
//1.创建哨兵位节点
struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
//2.维护两个指针cur1指向l1 ，cur2指向l2
struct ListNode* cur1 = l1, *cur2 = l2;
//维护一个tail指针指向新链表的尾节点
struct ListNode* tail = guard;
//3.进行比较
while(cur1 != NULL && cur2 != NULL)
{
if(cur1->val < cur2->val)
{
tail->next = cur1;//将cur1添加到新链表中
tail = cur1;//刷新新链表的尾节点
cur1 = cur1->next;//cur1向后移动一位
}
else
{
tail->next = cur2;
tail = cur2;
cur2 = cur2->next;
}
}
//4.当有一个链表走到NULL时
//当cur1为空,cur2就不为空
if(cur2)
tail->next = cur2;
else
tail->next = cur1;
//5.返回哨兵位的下一个节点
return guard->next;
}
struct ListNode* _mergeKLists(struct ListNode** lists, int left, int right)
{
//如果只有剩下个链表，则不需要继续分割和排序
if(left >= right)
return lists[left];
//找到中点
int mid = (left + right) / 2;
//沿着中点进行分割
struct ListNode* left_list = _mergeKLists(lists, left, mid);//左区间
struct ListNode* right_list = _mergeKLists(lists, mid + 1, right);//右区间
//合并两个排序链表
return mergeTwoLists(left_list,right_list);
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
//对应示例2
if(listsSize == 0)
return NULL;
//对应示例3
if(listsSize == 1 && lists[0] == NULL)
return NULL;
return _mergeKLists(lists, 0, listsSize - 1);
}