【leetcode】Sort List

Sort List
Sort a linked list in 
O
(
n
 log 
n
) time using constant space complexity.
 
 
체인 테이블을 병합 정렬하여 조작해야 한다.
 
병합 정렬 사상: 매번 체인 테이블의 중간 원소를 선택하여 체인 테이블을 두 부분으로 분할하고
체인 테이블의 요소가 질서정연할 때(즉 하나의 원소만 있을 때), 체인 테이블을 통합할 때까지 차례로 분할한다.
합병할 때, 매번 두 개의 체인 테이블 중의 작은 요소를 다음 위치에 놓는다.
 
 

 1 /**

 2  * Definition for singly-linked list.

 3  * struct ListNode {

 4  *     int val;

 5  *     ListNode *next;

 6  *     ListNode(int x) : val(x), next(NULL) {}

 7  * };

 8  */

 9 class Solution {

10 public:

11 

12     ListNode *mergeList(ListNode *h1,ListNode *h2)

13     {

14        ListNode *head=new ListNode(0);

15        ListNode *cur=head;

16        while(h1!=NULL&&h2!=NULL)

17        {

18            if(h1->val>h2->val)

19            {

20                cur->next=h2;

21                h2=h2->next;

22            }

23            else

24            {

25                cur->next=h1;

26                h1=h1->next;

27            }

28            

29            cur=cur->next;

30        }

31        

32        cur->next=h1==NULL?h2:h1;

33        

34        cur=head;

35        head=head->next;

36        delete cur;

37        

38        return head;

39     }

40     

41 

42     

43     ListNode *sortList(ListNode *head) {

44         

45         

46         if(head==NULL||head->next==NULL) return head;

47         

48         ListNode *slow,*fast;

49         slow=fast=head;

50         while(fast->next!=NULL&&fast->next->next!=NULL)

51         {

52             fast=fast->next->next;

53             slow=slow->next;

54         }

55         

56         ListNode *mid=slow->next;

57         slow->next=NULL;

58         

59         ListNode *h1=sortList(head);

60         ListNode *h2=sortList(mid);

61         return mergeList(h1,h2);

62         

63         

64     }

65 };