leetcode做题笔记148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

思路一：归并排序

c语言解法

struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {
    struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    struct ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;
    while (temp1 != NULL && temp2 != NULL) {
        if (temp1->val <= temp2->val) {
            temp->next = temp1;
            temp1 = temp1->next;
        } else {
            temp->next = temp2;
            temp2 = temp2->next;
        }
        temp = temp->next;
    }
    if (temp1 != NULL) {
        temp->next = temp1;
    } else if (temp2 != NULL) {
        temp->next = temp2;
    }
    return dummyHead->next;
}
 
struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) {
    if (head == NULL) {
        return head;
    }
    if (head->next == tail) {
        head->next = NULL;
        return head;
    }
    struct ListNode *slow = head, *fast = head;
    while (fast != tail) {
        slow = slow->next;
        fast = fast->next;
        if (fast != tail) {
            fast = fast->next;
        }
    }
    struct ListNode* mid = slow;
    return merge(toSortList(head, mid), toSortList(mid, tail));
}
 
struct ListNode* sortList(struct ListNode* head) {
    return toSortList(head, NULL);
}

分析：

本题要将链表排序，由于链表的特性，无法直接从中间进行修改，所以利用快慢指针将链表分为两部分，对两个子链表进行排序，通过递归不断将链表分为两部分，直到无法分为止，最后合并所有的链表，得到排序后的链表

思路二：转换为数组后进行排序再转换为链表

c语言解法(此解法有取巧的成分，但时间复杂度上优于思路一，故列出）

int cmp(const int* a,const int* b)
{
    return *(int*)a - *(int*)b;
}
 
struct ListNode* sortList(struct ListNode* head)
{
    int A[50000]={0};
    int i = 0;
    struct ListNode* tmp = head;
 
    for(i=0; tmp != NULL; i++)
    {
        A[i] = tmp->val;
        tmp = tmp->next;
    }
 
    qsort(A,i,sizeof(int),cmp);
 
    tmp = head;
 
    for(i=0; tmp != NULL;i++)
    {
         tmp->val = A[i];
         tmp = tmp->next;
    }
 
    return head;
}

分析：

第二种思路则是将原链表转换为数组后进行排序再转换为链表，此解法更加直观，同时数组排序更加熟悉，此处利用快速排序排序数组，最后返回排序好的链表即可解决

总结：

本题考察对链表的排序操作，利用归并排序即可解决，也可转换为数组后利用数组的方法解决。