148. Sort List
LeetCode
medium
оригинал: C#
#csharp
#leetcode
#linked-list
#medium
#recursion
#search
#sort
#two-pointers
Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.
Пример:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
C# решение
сопоставлено/оригиналpublic class Solution {
public ListNode SortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode mid = GetMid(head);
ListNode left = SortList(head);
ListNode right = SortList(mid);
return Merge(left, right);
}
private ListNode Merge(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = list1 != null ? list1 : list2;
return dummyHead.next;
}
private ListNode GetMid(ListNode head) {
ListNode midPrev = null;
while (head != null && head.next != null) {
midPrev = midPrev == null ? head : midPrev.next;
head = head.next.next;
}
ListNode mid = midPrev.next;
midPrev.next = null;
return mid;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public ListNode SortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode mid = GetMid(head);
ListNode left = SortList(head);
ListNode right = SortList(mid);
return Merge(left, right);
}
private ListNode Merge(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = list1 != null ? list1 : list2;
return dummyHead.next;
}
private ListNode GetMid(ListNode head) {
ListNode midPrev = null;
while (head != null && head.next != null) {
midPrev = midPrev == null ? head : midPrev.next;
head = head.next.next;
}
ListNode mid = midPrev.next;
midPrev.next = null;
return mid;
}
}Java решение
сопоставлено/оригиналclass Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode mid = getMid(head);
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
ListNode merge(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode();
ListNode tail = dummyHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
tail = tail.next;
} else {
tail.next = list2;
list2 = list2.next;
tail = tail.next;
}
}
tail.next = (list1 != null) ? list1 : list2;
return dummyHead.next;
}
ListNode getMid(ListNode head) {
ListNode midPrev = null;
while (head != null && head.next != null) {
midPrev = (midPrev == null) ? head : midPrev.next;
head = head.next.next;
}
ListNode mid = midPrev.next;
midPrev.next = null;
return mid;
}
}JavaScript решение
сопоставлено/оригиналvar sortList = function (head) {
if (!head || !head.next) return head;
let mid = getMid(head);
let left = sortList(head);
let right = sortList(mid);
return merge(left, right);
function merge(list1, list2) {
let dummyHead = new ListNode();
let tail = dummyHead;
while (list1 && list2) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = list1 ? list1 : list2;
return dummyHead.next;
}
function getMid(head) {
let midPrev = null;
while (head && head.next) {
midPrev = midPrev === null ? head : midPrev.next;
head = head.next.next;
}
let mid = midPrev.next;
midPrev.next = null;
return mid;
}
};Python решение
сопоставлено/оригиналclass Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
mid = self.getMid(head)
left = self.sortList(head)
right = self.sortList(mid)
return self.merge(left, right)
def merge(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummyHead = ListNode(0)
tail = dummyHead
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 if list1 else list2
return dummyHead.next
def getMid(self, head: Optional[ListNode]) -> Optional[ListNode]:
midPrev = None
while head and head.next:
midPrev = head if not midPrev else midPrev.next
head = head.next.next
mid = midPrev.next
midPrev.next = None
return midGo решение
сопоставлено/оригиналfunc sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
mid := getMid(head)
left := sortList(head)
right := sortList(mid)
return merge(left, right)
}
func merge(list1, list2 *ListNode) *ListNode {
dummyHead := &ListNode{}
tail := dummyHead
for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
tail.Next = list1
list1 = list1.Next
} else {
tail.Next = list2
list2 = list2.Next
}
tail = tail.Next
}
if list1 != nil {
tail.Next = list1
} else {
tail.Next = list2
}
return dummyHead.Next
}
func getMid(head *ListNode) *ListNode {
midPrev := (*ListNode)(nil)
for head != nil && head.Next != nil {
if midPrev == nil {
midPrev = head
} else {
midPrev = midPrev.Next
}
head = head.Next.Next
}
mid := midPrev.Next
midPrev.Next = nil
return mid
}Algorithm
1️⃣
Разделение списка (Фаза разделения):
Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка.
2️⃣
Сортировка подсписков и их объединение (Фаза слияния):
Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков.
3️⃣
Иллюстрация процесса сортировки:
Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.