Ежедневная проблема кодирования - сортировка связанного списка (постоянное пространство)

Это проблема кодирования, которую задали в Google.

Постановка проблемы: - Учитывая связанный список, как мы можем отсортировать его за O (nlogn) временную сложность.

Ввод: 4 - ›1 -› -3 - ›11

Вывод: -3 - ›1 -› 4 - ›11

Если пространство не является проблемой, мы можем легко перебрать связанный список, скопировать его в другой массив, а затем запустить сортировку слиянием и вуаля, у нас есть временная сложность O (nlogn) с O (n) Космос.

Но давайте теперь добавим еще одно ограничение. Что, если мы хотим получить отсортированный связанный список, но в пространстве O (logn) вкратце отсортировать связанный список на месте.

Прежде чем перейти к решению, давайте сделаем шаг назад и подумаем, как его достичь. Одно ясно в этом решении: поскольку нам нужно достичь временной сложности O (nlogn), мы будем использовать сортировку слиянием для нашей цели. А сортировка слиянием работает с концепцией «разделяй и властвуй».

Давайте посмотрим на диаграмму, чтобы лучше понять.

Подобно тому, как мы разбиваем массив на две половины, мы собираемся разделить наш связанный список на две половины.

Но в случае связанного списка загвоздка заключается в том, как определить элемент mid. Чтобы понять это, мы собираемся использовать два указателя: один медленный, а другой быстрый.

Медленный указатель делает один прыжок, а быстрый указатель дает две надежды за раз, и вы увидите, когда быстро достигнет конца связанного списка, в этот момент медленный указатель будет указывать на средний элемент.

Давайте посмотрим на фрагмент кода, чтобы лучше понять.

ListNode *slow = head, *fast = head->next; 
while(fast && fast->next) 
{ 
  slow = slow->next; 
  fast = fast->next->next; 
}

Если вы запустите приведенный выше код в нашем примере, вы увидите, что после завершения цикла медленный указатель будет узлом со значением -1, а быстрый - узлом со значением 11.

Теперь наш медленный указатель является нашим средним элементом, поэтому мы знаем, где разделить список. Итак, мы продолжаем разделять наш связанный список таким же образом, и после того, как мы достигли точки с одним элементом, оставшимся в списке, мы начинаем объединять все вместе и, выполняя объединение, мы упорядочиваем список в отсортированном массиве.

Пожалуйста, посмотрите на приведенный ниже фрагмент кода, чтобы лучше понять.

ListNode *mergeSort(ListNode *head) {
    if(!head || !head->next) return head;
    // get middle node
    // not right if write: *fast = head. Otherwise, {2,1} will not be sorted.
    ListNode *slow = head, *fast = head->next; 
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *left = head, *right = slow->next;
    slow->next = NULL;
    left = mergeSort(left);
    right = mergeSort(right);
    return merge(left, right);
}
ListNode *merge(ListNode *L, ListNode *R) {
    if(!L) return R;
    if(!R) return L;
    ListNode *h = NULL;
    if(L->val < R->val) {
        h = L;
        h->next = merge(L->next, R);
    } else {
        h = R;
        h->next = merge(L, R->next);
    }
    return h;
}