Решение задачи с собеседования Middle of the Linked List [+ ВИДЕО]04.08.2024 13:30

На видео более подробное объяснение каждого решения

Постановка задачи

Ссылка на задачу: https://leetcode.com/problems/middle-of-the-linked-list

Дан указатель head на начало односвязного списка, нужно вернуть средний узел списка.

Если средних узлов два, нужно вернуть второй средний узел.

1. Решение с использованием массива

Подход

Преобразование списка в массив упрощает доступ к элементам по индексу. Мы проходим по списку и сохраняем все узлы в массив, так как доступ по индексу в массиве осуществляется за постоянное время O(1). После этого мы легко можем найти средний элемент, просто взяв элемент по индексу len(items) // 2

Алгоритм

1. Пройти по списку и сохранить все его элементы в массив.

2. Определить индекс среднего элемента массива.

3. Вернуть элемент, находящийся по этому индексу.

Код решения

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        items = []

        while head: #None
            items.append(head)
            head = head.next
        
        return items[len(items) // 2]

Сложность алгоритма

• По времени: O (n), где n — количество элементов в списке.

• По памяти: O (n), так как мы сохраняем все элементы списка в массив.

Визуализация

1. Исходный список: 1 -> 2 -> 3 -> 4 -> 5

2. Массив после прохождения по списку: [1, 2, 3, 4, 5]

3. Индекс среднего элемента: 5 // 2 = 2

4. Средний элемент в массиве: 3
   0 1 2 3 4
[1, 2, {3}, 4, 5]

2. Решение с подсчетом длины списка

Подход

В этом подходе мы сначала считаем количество элементов в списке, чтобы точно знать, сколько узлов в нем содержится. Считая количество узлов, мы можем определить индекс среднего элемента как length // 2. Затем, проходя список во второй раз, мы останавливаемся на этом индексе и возвращаем соответствующий узел.

Алгоритм

1. Пройти по списку и подсчитать количество элементов.

1. Пройти по списку снова до среднего элемента и вернуть его.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        count = self.count(head)

        for _ in range(count // 2):
            head = head.next
        
        return head
    
    def count(self, head):
        res = 0
        while head:
            res += 1
            head = head.next
        return res

Сложность алгоритма

• По времени: O (n), где n — количество элементов в списке.

• По памяти: O (1), так как мы не используем дополнительную память.

Визуализация

1. Исходный список: 1 -> 2 -> 3 -> 4 -> 5

2. Проход 1: Подсчет длины списка

   • Длина списка: 5

3. Средний индекс: 5 // 2 = 2

4. Проход 2: Получение среднего элемента

   • Проходим через узлы до индекса, который мы вычислили на 3 шаге:

   1 (0), 2 (1), 3 (2)

5. Средний элемент: 3

3. Решение с использованием метода быстрого и медленного указателя

Подход

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

Алгоритм

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

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

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow

Сложность алгоритма

• По времени: O (n), где n — количество элементов в списке.

• По памяти: O (1), так как используем только два указателя.

Визуализация

1. Исходный список: 1 -> 2 -> 3 -> 4 -> 5

2. Начальное положение:

   • Медленный указатель (S) на 1

   • Быстрый указатель (F) на 1

3. Шаг 1:

   • S: 2 (двигается на 1 узел вперед)

   • F: 3 (двигается на 2 узла вперед)

   • Список: 1 -> [2 (S)] -> 3 -> [4 (F)] -> 5

4. Шаг 2:

   • S: 3 (двигается на 1 узел вперед)

   • F: 5 (двигается на 2 узла вперед)

   • Список: 1 -> 2 -> [3 (S)] -> 4 -> [5 (F)]

5. Конец:

   • Быстрый указатель (F) достигает конца списка или выходит за его пределы.

   • Медленный указатель (S) находится на 3, который и является средним элементом.

Итоговый результат: Средний элемент списка 3.

© Habrahabr.ru