LCR 077. 排序链表

LCR 077. 排序链表

---

题目链接：LCR 077. 排序链表

注：该题与 148. 排序链表 完全一样

代码如下：

class Solution {
public:
    ListNode* sortList(ListNode* head) 
    {
        return msort(head,nullptr);
    }

    ListNode* msort(ListNode* head,ListNode* tail)
    {
        if(head==nullptr)
            return head;

        if(head->next==tail)
        {
            head->next=nullptr;
            return head;
        }

        ListNode* mid=getMiddle(head,tail);

        return merge(msort(head,mid),msort(mid,tail));
    }

    ListNode* merge(ListNode* head1,ListNode* head2)
    {
        ListNode* Head=new ListNode;
        Head->next=nullptr;
        ListNode *temp=Head,*temp1=head1,*temp2=head2;

        while(temp1&&temp2)
        {
            if(temp1->val<temp2->val)
            {
                temp->next=temp1;
                temp1=temp1->next;
            }
            else
            {
                temp->next=temp2;
                temp2=temp2->next;
            }
            temp=temp->next;
        }

        if(temp1)
            temp->next=temp1;
        if(temp2)
            temp->next=temp2;

        return Head->next;
    }
    
    ListNode* getMiddle(ListNode* head,ListNode* tail)
    {
        ListNode* slow=head,*fast=head;

        while(fast!=tail)
        {
            slow=slow->next;
            fast=fast->next;
            if(fast!=tail)
                fast=fast->next;
        }
        return slow;
    }
};



/*
//直接插入排序，会超时
class Solution {
public:
    ListNode* sortList(ListNode* head) 
    {
        if(head==nullptr||head->next==nullptr)
            return head;

        ListNode *Head=new ListNode;
        Head->next=nullptr;
        Head->next=head;

        ListNode *p=Head->next,*pre;
        ListNode *r=p->next;
        p->next=nullptr;
        p=r;

        while(p)
        {
            pre=Head;
            r=p->next;

            while(pre->next&&pre->next->valval)
                pre=pre->next;

            p->next=pre->next;
            pre->next=p;

            p=r;
        }
        
        head=Head->next;
        delete Head;

        return head;
    }
};
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108