C# (C Sharp) programming

💡Задача: Сортировочный список



Условие: дан односвязный список, необходимо отсортировать узлы списка по значению в порядке возрастания



Пример:



Ввод: head = [4,2,1,3]

Вывод: [1,2,3,4]



Ввод: head = [-1,5,3,4,0]

Вывод: [-1,0,3,4,5]



Можете ли вы отсортировать связанный список за O (n logn) времени и O(1) памяти (т.е. постоянного пространства)?



Решение:



public class Solution

{

public ListNode SortList(ListNode head)

{

if (head == null)

return null;



if (head.next == null)

return head;



var tail = head;

var mid = head;

var prev = head;



while (tail != null && tail.next != null)

{

tail = tail.next.next;

prev = mid;

mid = mid.next;

}

prev.next = null;



return MergeTwoLists(SortList(head), SortList(mid));

}



ListNode MergeTwoLists(ListNode list1, ListNode list2)

{

var head = new ListNode();

var newNode = head;



while (list1 != null && list2 != null)

{

if (list1.val < list2.val)

{

newNode.next = list1;

newNode = list1;

list1 = list1.next;

}

else

{

newNode.next = list2;

newNode = list2;

list2 = list2.next;

}

}



newNode.next = list1 ?? list2;



return head.next;

}

}



пишите свое решение в комментариях 👇



@csharp_ci