题解 | #成绩排序#

• 整体的程序分为两步：两个链表之间的合并，以及对一组链表对折造成两两链表对

1. Merge(struct ListNode* pHead1, struct ListNode* pHead2 ):将两个链表进行合并
2. 将链表的数组进行对折，首尾进行一对链表的合并，进行迭代

// 合并两个链表
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    if(!pHead1)
        return pHead2;
    if(!pHead2)
        return pHead1;
     
    struct ListNode * ph1, * ph2,* p;
    struct ListNode * newHd = (struct ListNode *)malloc(sizeof(struct ListNode));
    p = newHd;
    p->next = NULL;
     
    ph1 = pHead1;
    ph2 = pHead2;
    
    while(ph1 && ph2)
    {
         
        if(ph1->val > ph2->val)
        {
            p->next = ph2;
            p = ph2;
            ph2 = ph2->next;
            p->next = NULL;
        }else
        {
            p->next = ph1;
            p = ph1;
            ph1 = ph1->next;
            p->next = NULL;
        }
    }  
    if(!ph1)
        p->next = ph2;
    if(!ph2)
        p->next = ph1;
     
    return newHd->next;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    int i = 0;
    //int n = listsLen - 1;

    while(listsLen / 2)
    {
        for(i = 0 ; i < listsLen / 2 ; i++)
        {
            lists[i] = Merge(lists[i],lists[listsLen - i - 1]);//listsLen长度随时变化，需要用listsLen标注
        }
        listsLen = (listsLen % 2)?(listsLen / 2 + 1):(listsLen / 2);
    }
    return lists[0];
}