跳转至

排序链表

最后更新：2023-12-02

链接：https://leetcode.cn/problems/sort-list/description/

题目描述

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

题目示例

输入： head = [4,2,1,3]

输出： [1,2,3,4]

输入： head = [-1,5,3,4,0]

输出： [-1,0,3,4,5]

输入： head = []

输出： []

提示：

  • 链表中节点的数目在范围 \([0, 5 * 10^4]\) 内
  • -\(10^5 <= Node.val <= 10^5\)

进阶：

你可以在 \(O(n log n)\) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

C
 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "uthash.h"

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/

#define MAX_ARR_LEN 102400

int comp(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}

struct ListNode* sortList(struct ListNode* head){
    struct ListNode* s = head;
    int tmp[MAX_ARR_LEN] = {0};
    int count = 0, i = 0;

    while ((count != MAX_ARR_LEN) && (s != NULL)) {
        tmp[count] = s->val;
        s = s->next;
        count++;
    }

    qsort(tmp, count, sizeof(int), comp);

    s = head;
    while ((i <= count) && (s != NULL)) {
        s->val = tmp[i];
        s = s->next;
        i++;
    }

    return head;
}
C
 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
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);
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
const maxArrLen = 102400

func sortList(head *ListNode) *ListNode {
    s := head
    count, i := 0, 0
    tmp := make([]int, 0)

    for count != maxArrLen && s != nil {
        tmp = append(tmp, s.Val)
        s = s.Next
        count++
    }

    sort.Ints(tmp)
    s = head
    for i <= count && s != nil {
        s.Val = tmp[i]
        s = s.Next
        i++
    }
    return head
}
Go
 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
func merge(head1, head2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    temp, temp1, temp2 := dummyHead, head1, head2
    for temp1 != nil && temp2 != nil {
        if temp1.Val <= temp2.Val {
            temp.Next = temp1
            temp1 = temp1.Next
        } else {
            temp.Next = temp2
            temp2 = temp2.Next
        }
        temp = temp.Next
    }
    if temp1 != nil {
        temp.Next = temp1
    } else if temp2 != nil {
        temp.Next = temp2
    }
    return dummyHead.Next
}

func sort(head, tail *ListNode) *ListNode {
    if head == nil {
        return head
    }

    if head.Next == tail {
        head.Next = nil
        return head
    }

    slow, fast := head, head
    for fast != tail {
        slow = slow.Next
        fast = fast.Next
        if fast != tail {
            fast = fast.Next
        }
    }

    mid := slow
    return merge(sort(head, mid), sort(mid, tail))
}

func sortList(head *ListNode) *ListNode {
    return sort(head, nil)
}