Сортировка односвязного списка

/**
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public static ListNode SortLinkedList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // Разделение списка на две половины
        (ListNode, ListNode) Split(ListNode head) {
            ListNode slow = head;
            ListNode fast = head.next;
            
            // Техника быстрого и медленного указателя
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            
            ListNode mid = slow.next;
            slow.next = null; // Разрываем связь
            return (head, mid);
        }
        
        // Слияние двух отсортированных списков
        ListNode Merge(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(0); // Фиктивная нода
            ListNode current = dummy;
            
            // Выбираем меньший элемент на каждом шаге
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    current.next = l1;
                    l1 = l1.next;
                } else {
                    current.next = l2;
                    l2 = l2.next;
                }
                current = current.next;
            }
            
            // Добавляем оставшиеся элементы
            current.next = l1 ?? l2;
            return dummy.next;
        }
        
        // Рекурсивная сортировка слиянием
        ListNode MergeSort(ListNode head) {
            // Базовый случай
            if (head == null || head.next == null) {
                return head;
            }
            
            var (left, right) = Split(head);
            ListNode leftSorted = MergeSort(left);
            ListNode rightSorted = MergeSort(right);
            return Merge(leftSorted, rightSorted);
        }
        
        return MergeSort(head);
    }
}

#include <vector>

using namespace std;

/**
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

// Объявляем функцию заранее для рекурсивного вызова
ListNode* mergeSortImpl(ListNode* head, auto& split, auto& merge);

ListNode* sortLinkedList(ListNode* head) {
    if (!head || !head->next) return head;
    
    auto split = [](ListNode* head) -> pair<ListNode*, ListNode*> {
        ListNode* slow = head;
        ListNode* fast = head->next;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        ListNode* mid = slow->next;
        slow->next = nullptr;
        return {head, mid};
    };
    
    auto merge = [](ListNode* l1, ListNode* l2) -> ListNode* {
        auto dummy = make_unique<ListNode>(0);
        ListNode* current = dummy.get();
        
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                current->next = l1;
                l1 = l1->next;
            } else {
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }
        
        current->next = l1 ? l1 : l2;
        return dummy->next;
    };
    
    return mergeSortImpl(head, split, merge);
}

ListNode* mergeSortImpl(ListNode* head, auto& split, auto& merge) {
    if (!head || !head->next) return head;
    
    auto [left, right] = split(head);
    ListNode* leftSorted = mergeSortImpl(left, split, merge);
    ListNode* rightSorted = mergeSortImpl(right, split, merge);
    return merge(leftSorted, rightSorted);
}

package main

/**
 * type ListNode struct {
 *     Val  int
 *     Next *ListNode
 * }
 */

func sortLinkedList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    // Разделение списка на две половины
    split := func(head *ListNode) (*ListNode, *ListNode) {
        slow, fast := head, head.Next
        // Быстрый указатель движется в два раза быстрее
        for fast != nil && fast.Next != nil {
            slow = slow.Next
            fast = fast.Next.Next
        }
        mid := slow.Next
        slow.Next = nil // Разрываем связь
        return head, mid
    }
    
    // Слияние двух отсортированных списков
    merge := func(l1, l2 *ListNode) *ListNode {
        dummy := &ListNode{} // Фиктивная нода
        current := dummy
        
        // Выбираем меньший элемент на каждом шаге
        for l1 != nil && l2 != nil {
            if l1.Val <= l2.Val {
                current.Next = l1
                l1 = l1.Next
            } else {
                current.Next = l2
                l2 = l2.Next
            }
            current = current.Next
        }
        
        // Добавляем оставшиеся элементы
        if l1 != nil {
            current.Next = l1
        } else {
            current.Next = l2
        }
        
        return dummy.Next
    }
    
    // Рекурсивная сортировка слиянием
    var mergeSort func(*ListNode) *ListNode
    mergeSort = func(head *ListNode) *ListNode {
        // Базовый случай
        if head == nil || head.Next == nil {
            return head
        }
        
        left, right := split(head)
        leftSorted := mergeSort(left)
        rightSorted := mergeSort(right)
        return merge(leftSorted, rightSorted)
    }
    
    return mergeSort(head)
}

import java.util.*;

/**
 * class ListNode {
 *     Integer val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(Integer val) { this.val = val; }
 *     ListNode(Integer val, ListNode next) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public ListNode sortLinkedList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // Разделяем список на две половины
        ListNode[] halves = split(head);
        
        // Рекурсивно сортируем каждую половину
        ListNode leftSorted = sortLinkedList(halves[0]);
        ListNode rightSorted = sortLinkedList(halves[1]);
        
        // Сливаем отсортированные половины
        return merge(leftSorted, rightSorted);
    }
    
    // Разделение списка на две половины
    private ListNode[] split(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        
        // Техника быстрого и медленного указателя
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode mid = slow.next;
        slow.next = null; // Разрываем связь
        return new ListNode[]{head, mid};
    }
    
    // Слияние двух отсортированных списков
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(); // Фиктивная нода
        ListNode current = dummy;
        
        // Выбираем меньший элемент на каждом шаге
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        // Добавляем оставшиеся элементы
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

import java.util.*;

/**
 * class ListNode {
 *     Integer val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(Integer val) { this.val = val; }
 *     ListNode(Integer val, ListNode next) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public ListNode sortLinkedList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // Разделяем список на две половины
        ListNode[] halves = split(head);
        
        // Рекурсивно сортируем каждую половину
        ListNode leftSorted = sortLinkedList(halves[0]);
        ListNode rightSorted = sortLinkedList(halves[1]);
        
        // Сливаем отсортированные половины
        return merge(leftSorted, rightSorted);
    }
    
    // Разделение списка на две половины
    private ListNode[] split(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        
        // Техника быстрого и медленного указателя
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode mid = slow.next;
        slow.next = null; // Разрываем связь
        return new ListNode[]{head, mid};
    }
    
    // Слияние двух отсортированных списков
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(); // Фиктивная нода
        ListNode current = dummy;
        
        // Выбираем меньший элемент на каждом шаге
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        // Добавляем оставшиеся элементы
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

from list_node import ListNode

# class ListNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next

def sort_linked_list(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    
    # Разделение списка на две половины
    def split(head: ListNode):
        # Используем технику "быстрый и медленный указатель"
        # для нахождения середины списка
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next  # Вторая половина списка
        slow.next = None  # Разрываем связь между половинами
        return head, mid
    
    # Слияние двух отсортированных списков
    def merge(l1: Optional[ListNode], l2: Optional[ListNode]):
        dummy = ListNode(0)  # Фиктивная начальная нода
        current = dummy
        
        # Сливаем списки, выбирая меньший элемент на каждом шаге
        while l1 and l2:
            if l1.val <= l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        
        # Добавляем оставшиеся элементы
        current.next = l1 if l1 else l2
        return dummy.next
    
    # Рекурсивная сортировка слиянием
    def merge_sort(head: Optional[ListNode]):
        # Базовый случай: список пуст или содержит один элемент
        if not head or not head.next:
            return head
        
        # Разделяем список на две половины
        left, right = split(head)
        # Рекурсивно сортируем каждую половину
        left_sorted = merge_sort(left)
        right_sorted = merge_sort(right)
        # Сливаем отсортированные половины
        return merge(left_sorted, right_sorted)
    
    return merge_sort(head)