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

Метод 1: подсчет узлов и разделение
Один простой способ разделения связанного списка — подсчитать общее количество узлов и затем разделить их на две равные половины. Вот пример реализации на Python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def split_linked_list(head):
    # Count the number of nodes
    count = 0
    curr = head
    while curr:
        count += 1
        curr = curr.next
    # Determine the midpoint
    mid = count // 2
    # Traverse to the midpoint
    curr = head
    for _ in range(mid - 1):
        curr = curr.next
    # Split the list into two halves
    second_half = curr.next
    curr.next = None
    return head, second_half

Метод 2: подход с медленным и быстрым указателем.
Другой популярный метод разделения связанного списка — использование подхода с медленным и быстрым указателем. Этот метод предполагает перемещение связанного списка с помощью двух указателей, один из которых движется вдвое медленнее другого. Когда быстрый указатель достигнет конца списка, медленный указатель окажется в средней точке. Давайте посмотрим код:

def split_linked_list(head):
    slow_ptr = head
    fast_ptr = head
    prev = None
    while fast_ptr and fast_ptr.next:
        prev = slow_ptr
        slow_ptr = slow_ptr.next
        fast_ptr = fast_ptr.next.next
    # Split the list into two halves
    second_half = slow_ptr
    prev.next = None
    return head, second_half

Метод 3: рекурсивный подход
Мы также можем рекурсивно разделить связанный список, многократно разделив его на две половины. Вот пример реализации на Python:

def split_linked_list(head):
    if head is None or head.next is None:
        return head, None
    slow_ptr = head
    fast_ptr = head.next
    while fast_ptr and fast_ptr.next:
        slow_ptr = slow_ptr.next
        fast_ptr = fast_ptr.next.next
    second_half = slow_ptr.next
    slow_ptr.next = None
    return head, second_half

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