24.08.2024 13:39
idsulik 33 2400 Источник

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

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

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

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

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

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

Описание решения

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

  2. Заполнение массива: Пройдя по всему списку, мы добавляем каждый узел в массив. В результате массив nodes будет содержать все узлы в порядке их появления в списке.

  3. Перепривязка указателей: Пройдя по массиву слева направо, начиная со второго элемента, мы устанавливаем для каждого узла next указатель на предыдущий элемент в массиве.

  4. Обнуление указателя next у первого элемента: Так как первый элемент в массиве (который был последним узлом списка) должен стать последним узлом перевернутого списка, его указатель next должен быть установлен в None.

  5. Возвращаем новый head: В конце мы возвращаем последний элемент массива как новый head перевернутого списка.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:  # Если список пуст, возвращаем None
            return None

        nodes = []  # Массив для хранения узлов
        while head:
            nodes.append(head)  # Добавляем узел в массив
            head = head.next  # Переходим к следующему узлу
        
        for i in range(1, len(nodes)):
            node = nodes[i]
            # Устанавливаем указатель next
            node.next = nodes[i - 1]

        # Устанавливаем None для последнего элемента в перевернутом списке
        nodes[0].next = None  

        return nodes[-1]  # Возвращаем новый head

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

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

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

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

Давайте рассмотрим визуализацию работы алгоритма на примере списка
1 -> 2 -> 3 -> 4 -> 5 -> NULL

  1. Инициализация пустого массива nodes:

    • Начинаем с пустого массива: nodes = [].

  2. Заполнение массива узлами списка:

    • Проходим по исходному списку и добавляем каждый узел в массив:

    • После первого шага: nodes = [1] (где 1 — это ссылка на узел списка с значением 1)

    • После второго шага: nodes = [1, 2]

    • После третьего шага: nodes = [1, 2, 3]

    • После четвертого шага: nodes = [1, 2, 3, 4]

    • После пятого шага: nodes = [1, 2, 3, 4, 5]

    Теперь массив nodes содержит ссылки на все узлы списка в исходном порядке.

  3. Перепривязка указателей next:

    • Теперь мы идем по массиву, начиная со второго индекса, и для каждого узла устанавливаем его next указатель на предыдущий узел в массиве.

    • Для узла 2 (второго элемента массива): nodes[1].next = nodes[0]

    Новый список: 2 <-> 1 (первый узел все еще ссылается на второй, поэтому связь идет в обе стороны, цикличная связь)

    • Для узла 3 (третьего элемента массива): nodes[2].next = nodes[1]

    Новый список: 3 -> 2 <-> 1

    • Для узла 4 (четвертого элемента массива): nodes[3].next = nodes[2]

    Новый список: 4 -> 3 -> 2 <-> 1

    • Для узла 5 (пятого элемента массива): nodes[4].next = nodes[3]

    Новый список: 5 -> 4 -> 3 -> 2 <-> 1

    В этот момент все узлы, начиная со второго, указывают на предыдущие узлы в новом порядке.

  4. Обнуление указателя next для первого узла массива:

    • Поскольку первый элемент массива теперь последний в новом списке, его next указатель должен быть None.
    nodes[0].next = None

    Теперь первый узел (бывший 1 -> NULL) становится последним: 5 -> 4 -> 3 -> 2 -> 1 -> NULL.

  5. Возвращаем новый head списка:

    • Последний элемент массива nodes[-1], который содержит узел с значением 5, теперь становится новым head списка.

    В итоге, исходный список 1 -> 2 -> 3 -> 4 -> 5 -> NULL превращается в перевернутый список 5 -> 4 -> 3 -> 2 -> 1 -> NULL.

2. Решение с использованием метода двух указателей

Подход

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

Алгоритм

  1. Инициализация указателя prev:
    Мы начинаем с указателя prev, который изначально равен None. Этот указатель будет использоваться для хранения предыдущего узла в перевернутом списке.

  2. Проход по списку:

    Мы проходим по списку, изменяя указатели next каждого узла, чтобы они указывали на предыдущий узел (prev). Для этого в цикле мы выполняем следующие шаги:

    • Сохраняем указатель на следующий узел (tmp = head.next), чтобы не потерять его после изменения head.next.

    • Изменяем текущий указатель next узла head, чтобы он указывал на prev.

    • Перемещаем prev на текущий узел (prev = head).

    • Перемещаем head на следующий узел (head = tmp).

  3. Возвращаем новый head:

    После завершения прохода по списку prev будет указывать на последний узел исходного списка, который теперь станет head перевернутого списка.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None  # Инициализация указателя на предыдущий узел
        
        while head:
            tmp = head.next  # Сохраняем указатель на следующий узел
            head.next = prev  # Разворачиваем текущий узел
            prev = head  # Смещаем указатель prev на текущий узел
            head = tmp  # Переходим к следующему узлу
        
        return prev  # Возвращаем новый head списка

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

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

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

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

Рассмотрим исходный список 1 -> 2 -> 3 -> 4 -> 5 -> NULL.

  1. Инициализация:

    prev = None, head = 1.

  2. Первый шаг цикла:

    • tmp = 2 (сохраняем следующий узел)

    • head.next = None (разворачиваем указатель 1 -> NULL)

    • prev = 1, head = 2.

    Состояние: 1 -> NULL, 2 -> 3 -> 4 -> 5 -> NULL.

  3. Второй шаг цикла:

    • tmp = 3 (сохраняем следующий узел)

    • head.next = 1 (разворачиваем указатель 2 -> 1)

    • prev = 2, head = 3.

    Состояние: 2 -> 1 -> NULL, 3 -> 4 -> 5 -> NULL.

  4. Повторяем до конца:

    После завершения всех шагов получаем перевернутый список: 5 -> 4 -> 3 -> 2 -> 1 -> NULL.

Комментарии (33)


  1. idsulik Автор
    24.08.2024 13:41
    #27202820

    Буду благодарен за обратную связь, критика приветствуется, желательно аргументированная!)


    1. bromzh
      24.08.2024 13:41
      #27202842
      +4

      Сколько раз в кодовой базе Avito разворачивается список (примерно)? Насколько часто в рабочих задачах приходится его развернуть? Вы используете какую-то библиотеку для этого, или самописное решение?


      1. vvviperrr
        24.08.2024 13:41
        #27202874
        +1

        лучше бы проверяли, сможет ли кандидат изменить размер процента от продажи товара на площадке. еще ценится умение отписаться от клиента, если товар потерян доставкой. а не вот это вот все.


        1. idsulik Автор
          24.08.2024 13:41
          #27202884

          сарказм?)


      1. idsulik Автор
        24.08.2024 13:41
        #27202882

        Мне эту задачу давалю на интервью, используют ли они это на деле - вряд ли)


  1. datacompboy
    24.08.2024 13:41
    #27203106

    А где векторизация? Где тестирование на терабайтных списках?....

    https://habr.com/ru/articles/682332/ & https://habr.com/ru/articles/688874/


    1. idsulik Автор
      24.08.2024 13:41
      #27203132

      Не дорос еще)


  1. idsulik Автор
    24.08.2024 13:41
    #27203316

    А кто обиделся и ставит минусы?))


    1. nickolaym
      24.08.2024 13:41
      #27203448
      +2

      Одни ставят минусы, а кое-кто другой обиделся.


      1. idsulik Автор
        24.08.2024 13:41
        #27203520

        Я?) с чего вы взяли? стало интересно кто просто лепит минусы на все подряд)


        1. nickolaym
          24.08.2024 13:41
          #27205930

          А с чего вы взяли, что кто-то лепит минусы на всё подряд?


          1. idsulik Автор
            24.08.2024 13:41
            #27206144

            На тот момент было несколько комментов и на все мои разом поставили минусы) даже на безобидный комментарий - "Буду благодарен за обратную связь, критика приветствуется, желательно аргументированная!)"


  1. nickolaym
    24.08.2024 13:41
    #27203492

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

    Сама по себе задача очень простая (на литкоде имеет уровень easy). Это значит, что обсуждать её есть смысл, когда есть что добавить интересного к эталонному решению. Ну вот выше уже упомянули про терабайтные наборы. Или, например, обсудить существенно разные реализации (в существенно разных языках - или в разных парадигмах на одном и том же питоне). Или ещё что-нибудь... Иначе это как-то не соответствует заявленному автором званию Senior.

    Уже сам по себе старт: "давайте сделаем дефолтную реализацию с O(n) дополнительной памяти, а потом разгоним" выглядит странно. Ну ок, тогда давайте поиграем в другой жанр, в ненормальное программирование: найти самый медленный и прожорливый алгоритм? Есть же соревнование в замедлении сортировки, почему бы и в замедление разворота списка не посоревноваться?

    В общем, решение на пятёрочку, а статья на двоечку с плюсом. За это и минусы. А не за мифические обидки.


    1. idsulik Автор
      24.08.2024 13:41
      #27203532

      1. Окей

      2. Мне когда-то попалась эта задача и я не знал как решить, теперь решил рассказать другим как это сделать, визуальное объяснение, каждому подойдет свой вариант подачи материала, надеюсь моя подача тоже будет полезна кому-то. Причем тут мое звание Senior? Где в задаче это упоминается?) Если я Senior, то должен объяснять только hard задачи? Не вижу логики

      3. Если странно, предложите идею как сделать лучше

      4. Я не про минус на статью писал, а про минус на каждый мой коммент) Если подскажете как сделать статью лучше, пишите. Не про террабайты, а именно эту задачу с ограничениями из литкода


      1. nickolaym
        24.08.2024 13:41
        #27206038

        Ну блин, если бы вам предложили решить какую-нибудь простенькую задачку по математике, которую почему-то вы забыли, как решали в 9 классе, - то тоже бы расписали? Для 9-классника это норма, для 8-классника это подвиг, для сеньора - это детство.

        Я на ютубе встречал каналы по математике с таким контентом, но их ведут репетиторы для школьников, там очень адресная аудитория.

        И, на мой взгляд, "один ролик/пост - одна задачка" - это хлебный мякиш. Либо задача должна быть со звёздочками, либо охват предмета должен быть большой: например, класс задач и системный подход к ним, или всевозможные закоулки одной задачи.

        Вот, например, алгоритмы бисекции содержат такие закоулки (граничные условия), и наивная реализация "с листа" у многих программистов получается с багами. Можно ли такое сказать про переворот списка?

        Я-то, как раз, могу раскрыть тему. Но статью писать мне, пардон, лень. Это надо план изложения продумать и всё такое.

        Могу накидать направления работы:

        • как решать эту задачу с мутабельными и иммутабельными структурами (с мутабельными уже показано)

        • виды циклов и рекурсий

        • выразительные возможности разных языков (а не единственное решение в духе "на любом языке можно писать на фортране")


        1. idsulik Автор
          24.08.2024 13:41
          #27206154

          Есть же профессора, которые сидят на ютуб и объясняют как решать задачи 9-го класса и таких очень много, на ваш взгляд это глупо это делать? Но это ваш взгляд.
          Для каждого контента свой потребитель, если вам нужны решения сложных задач, то либо решите сами и расскажите, либо ждите кого-то, кто это сделает)


          1. nickolaym
            24.08.2024 13:41
            #27206260

            Как решать задачИ - vs как решить задачУ. Я уже написал выше.

            Решение этой задачи разными способами я привёл в комментарии, но кому-то оно не понравилось, - обиделся, наверное ;)

            Ну а рассказывать решения конкретных задач с литкода - я считаю неэтичным. Может быть, если мне когда-то будет не лень, я расскажу некоторые общие подходы. Они там есть. Но период лютого увлечения литкодом у меня был пару лет назад.

            Вообще же, литкод уровня медиум и хард - это такое олимпиадное программирование. Говнокодить write-only, лишь бы пролезло по ограничениям на производительность, - ради бога.

            Один раз по приколу я сграбил все тестовые входные данные и написал табличное решение, и его засчитали, ахаха. Куда уж оптимальнее.


            1. idsulik Автор
              24.08.2024 13:41
              #27206304

              Решение этой задачи разными способами я привёл в комментарии, но кому-то оно не понравилось, - обиделся, наверное ;)

              Если вы про этот комментарий https://habr.com/ru/articles/838270/comments/#comment_27203550 , то я не увидел там оптимизации, можете ткнуть пальцем в каком месте решение оптимальнее, чем второй решение в статье?

              Ну а рассказывать решения конкретных задач с литкода - я считаю неэтичным. Может быть, если мне когда-то будет не лень, я расскажу некоторые общие подходы. Они там есть. Но период лютого увлечения литкодом у меня был пару лет назад.

              ваше мнение, имеет место быть) но я в свое время смотрел как другие решают и это мне сильно помогло, решил тоже внести свой вклад.

              Последние два абзаца я не понял к чему) ну и в принципе не понял негатива по отношению к этой статье, если вам она не полезна, то найдутся люди, которым она полезна. Если у вас есть конкретный фидбек, как можно сделать статью более полезной для НОВИЧКОВ, просьба написать, буду благодарен. Эта статья не рассчитана на тех, кто как семечки щелкает подобные задачи, коих тут много, насколько я понял и к сожалению они не видят дальше своего носа, думают, что если им все понятно, то и остальным должно быть)


  1. Farongy
    24.08.2024 13:41
    #27203526

    А можно в перерывах между разворачиваниями списков, сделать нормальные фильтры?!


    1. idsulik Автор
      24.08.2024 13:41
      #27203538

      Фильтры чего? Не понял вопроса


  1. nickolaym
    24.08.2024 13:41
    #27203550

    Просто покажу, как можно на ровном месте сделать чуть красивее.

    def revert_sequential_and_verbose(head):
  prev = None
  while head:
    tmp = head.next
    head.next = prev
    prev = head
    head = tmp
  return prev

def revert_using_tuple_assign(head):
  prev = None
  while head:
    head, prev, head.next = head.next, head, prev
  return prev

    А можно чуть изощрённее, - избавиться от цикла while на верхнем уровне

    def iterate_single_linked(head):
  while head:
    #####################
    # здесь был спойлер #
    #####################

def revert_using_for_loop(head):
  prev = None
  for curr in iterate_single_linked(head):
    curr.next, prev = prev, curr
  return prev

def revert_using_reduce(head):
  def op(prev, curr):
    #####################
    # здесь был спойлер #
    #####################
  return functools.reduce(op, iterate_single_linked(head), None)

    Разумеется, использование генераторов и ФВП (и даже кортежей) на питоне вносит лишние накладные расходы по сравнению с наивным строго последовательным "сишно-фортрановым" решением. Но, тем не менее...

    Вот, что мы бы тут ожидали увидеть на хабре от автора.


    1. idsulik Автор
      24.08.2024 13:41
      #27203614

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

      Если вы знаете как решить лучше - отлично, объясните данное решение, напишите статью, чтобы другие могли понять плюсы и минусы, вуаля


      1. SpiderEkb
        24.08.2024 13:41
        #27204520

        // head -> node1 -> node2 -> node3 -> nullptr
reverseList(Node* head)
{
  // это будет это будет нового списка
  // newHead = head
  Node* newHead = head;
  
  // следующий после головного узел
  // headNext = node1
  Node* headNext = head->next;
  
  // временная переменная
  Node* tmp;
  
  // этот узел будет последним с развернутом списке
  // head -> nullptr
  head->next = nullptr;
  
  while (headNext != nullptr) {
    // запомним указатель "через узел"
    // 1 tmp = node2
    // 2 tmp = node3
    // 3 tmp = nullptr
    tmp = headNext->next;
    
    // прицепляем головной узел к следующему за ним
    // 1 node1 -> head -> nullptr
    // 2 node2 -> node1 -> head -> nullptr
    // 3 node3 -> node2 -> node1 -> head -> nullptr
    headNext->next = newHead;
    
    // делаем следующий после начала узел "головным"
    // 1 newHead = node1
    // 2 newHead = node2
    // 3 newHead = node3
    newHead = headNext;
    
    // теперь то, что было "через узел", становится следующим
    // 1 headNext = node2
    // 2 headNext = node3
    // 3 headNext = nullptr
    headNext = tmp;
  };
  
  return newHead;
}

        Тоже самое на С. Тут комментариев больше чем кода. Просто. Оптимально. Минимум накладных расходов. Минимум кода (больше комментариев).

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

        P.S. до этого такую задачу не решал, написал первое, что в голову пришло пока читал. Потом уже увидел что такое решение уже было предложено.

        P.P.S. сама по себе задача бессмысленная. Если вам нужно ходить по списку туда-сюда - есть двусвязные списки. С необходимостью разворачивать односвязный список за 30+ лет практики не сталкивался ни разу. Хотя со списками приходилось работать много в самых разных их реализациях.


        1. idsulik Автор
          24.08.2024 13:41
          #27204718
          +1

          И к чему вы это?) вы смогли решить это, круто, но есть тысячи других, кто не смог и им нужна помощь, среди них был и я когда-то.
          Но на хабре всегда думают, что все всё знают)) ну или думаю, что если они знают, то не надо писать об этом для других


          1. SpiderEkb
            24.08.2024 13:41
            #27204820

            Если хотите помочь - ну предлагайте действительно хорошее решение. А не вот это вот с массивами.

            Просто представьте, что вам надо развернуть список из 10 000 000 элементов...

            Два поста с оптимальным (по простоте и эффективности) решением - оба с минусами.


            1. idsulik Автор
              24.08.2024 13:41
              #27204848
              +1

              там ведь два решения, один с массивом, а другой оптимальный, что не нравится?

              мое второе решение даже проще, чем то, что вы написали выше

              Ощущение, что прочли половину статьи и решили выплеснуть свое недовольство)

              Либо даете аргументированный фидбек, либо пишете свою статью с блэк-джеком и шлюхами, все просто)


      1. nickolaym
        24.08.2024 13:41
        #27206212

        Параметры для оптимизации скажите. Вы ведь, как сеньор, знаете, что их несколько.

        1) Скорость исполнения. Тут фортран и фортранный стиль рулят.

        2) Устойчивость к ошибкам. Тут надо заметно сдвигаться в сторону функциональщины.

        3) Читаемость и сопровождаемость. Посреди между фортраном и фп.

        Движок литкода смотрит только на скорость исполнения. Но для задач уровня easy это вообще ни разу не является критерием. Можно, конечно, поучаствовать в олимпиаде "ваше решение выполнилось быстрее и сожрало меньше памяти, чем 99.99% других", но для питона перфтесты слишком шумят. А может, там сам тестовый стенд криво настроен и плохо изолирован. Сами убедитесь, запустите ваше решение десять раз и получите десять разных измерений.

        Я сейчас запостил и ваше, и мои решения, - и внезапно мои оказались капельку быстрее.


        1. idsulik Автор
          24.08.2024 13:41
          #27206226

          Я лишь знаю о существовании fortran и ничего более. Предложите решение оптимальнее, чем второе решение в статье, тогда и поговорим)


          1. nickolaym
            24.08.2024 13:41
            #27206300

            Я уже предложил в комментарии. Кортежи работают эффективнее последовательных присваиваний. Но вы только и знаете, что лепить минусы.


  1. GoodGod
    24.08.2024 13:41
    #27205502

    Спасибо за интересные статьи. А что вы собираете делать дальше? 1) Вы станете евангелистом алгоритм собеседований Российских компаний? Т.е. всегда будете знать актуальные алгоритмические собеседования в Российские компании и публиковать их и разбирать их? 2) Или вы будете вести тренинги по алгоритмам в Российские компании?


    1. idsulik Автор
      24.08.2024 13:41
      #27205688

      Спасибо!

      Почему именно российские, практически все задачи из разных faang(faang like) компаний, российских и зарубежных.

      А насчет будущего, пока не думал об этом, если не выгорю, может буду дальше это развивать, обучать алгоритмам в роли ментора и т.д.


  1. Sly_tom_cat
    24.08.2024 13:41
    #27212344

    В постановке еще не определено что должна возвращать функция reverse: это может быть как и оригинальный список с развернутыми указателями так и новый список с копиями элементов оригинального списка (оригинальный список при этом сохраняется в первичном состоянии).

    В зависимости от этого и решения могут не все подойти из озвученных выше. А вот не озвученные могут как раз подойти.

    Т.е. без доп памяти O(n) может и не обойтись. А неоднозначность постановки может привести и к спорным вариантам когда интервьюер предполагает одно а интервьюируемый - другое. Т.е. сам вопрос с подвохом....


    1. nickolaym
      24.08.2024 13:41
      #27212780

      Это литкод и уровень easy. Сгодится абсолютно любое решение.

      Проверяльщик смотрит там лишь на то, чтобы поля val у списка результатов были равны ожидаемым. Типизация утиная, можно вместо ListNode вернуть TsilEdon - и он сожрёт.

      На эрланге в принципе не получится вернуть не копию. А на питоне можно и так и этак.

      Причём стресс-теста для этой задачи нет, O(n) по памяти отлично проходит.

      А вот алгоритмом маляра Шлемюэля я проверяльщика не удосужился проверить, хотя думаю, что и O(n^2) по времени тоже пролезет, ну будет в общем зачёте первое место с конца.