leetcode l 체인 테이블 정렬 (체인 테이블 중간 노드, 체인 테이블 통합)

시간 복잡도
링크:https://www.nowcoder.com/questionTerminal/d75c232a0405427098a8d1627930bea6출처: 우객망
병합 정렬의 일반적인 단계는 다음과 같습니다.
1) 정렬 대기 수조(체인표)를 중점으로 하고 둘로 나눈다.
2) 왼쪽 부분을 차례로 병합 정렬한다.
3) 귀착적으로 오른쪽 부분을 병합 정렬한다.
4) 두 부분을 합쳐서 결과를 얻는다.
 
그래서 이 문제에 대응하면 세 가지 작은 문제로 나눌 수 있다.
1) 체인 시계의 중점을 찾는다(빠른 바늘 사고방식, 빠른 바늘은 한 번에 두 걸음, 느린 바늘은 한 번에 한 걸음, 빠른 바늘은 체인 시계의 끝에 있을 때 느린 바늘은 체인 시계의 중점에 딱 맞다).
2) merge 함수, 즉 체인 테이블을 어떻게 통합하는지 쓴다.(merge-two-sorted-lists 문제 해석 참조)
3) mergesort 함수를 작성하여 상기 절차를 실현한다.

 ListNode* findMiddle(ListNode *head){
        ListNode* pPrev=head;
        ListNode* pBehind =head->next;
        while(pBehind->next!= nullptr && pBehind != nullptr){// 
            pPrev = pPrev->next;
            pBehind =pBehind->next->next;
        }
        return pPrev;
    }


    ListNode *mergeList(ListNode* l1,ListNode*l2)
    {
        if(l1 == nullptr )
            return l2;
        if(l2 == nullptr)
            return l1;
        ListNode * head = new ListNode(0);
        ListNode * node =head;
        while(l1 != nullptr && l2 != nullptr){
            if(l1->val < l2->val){
                node->next=l1;
                l1 =l1->next;
            }
            else {
                node->next =l2;
                l2=l2->next;
            }
            node=node->next;
        }
        if(l1 != nullptr)
            node->next =l1;
        if(l2 != nullptr)
            node->next =l2;
        return head->next;
    }

// 
ListNode* recursion_merge(ListNode*l1,ListNode*l2){
        if(l1 ==nullptr)
            return l2;
        if(l2 == nullptr)
            return l1;
        ListNode * pMerge =nullptr;
        if(l1->val < l2->val){
            pMerge=l1;
            pMerge->next=recursion_merge(l1->next,l2);
        }else{
            pMerge=l2;
            pMerge->next=recursion_merge(l1,l2->next);
        }
        return pMerge;
    }


    ListNode *sortList(ListNode *head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode * middle = findMiddle(head);
        ListNode* right = sortList(middle->next);
        middle->next =nullptr;
        ListNode* left = sortList(head);
        return mergeList(left,right);
    }