Java Обратный связный список

RedDeveloper
04.01.2023 13:05
Java Обратный связный список

Как развернуть связный список в java?

Вход : head → 10 → 8 → 1 → 11 → null

Выход: head → 11 → 1 → 8 → 10 → null

Алгоритм →

ListNode current = head;
ListNode previous = null;
ListNode next = null;
while (current != null) {
    next = current.next;
    current.next = previous;
    previous = current;
    current = next;
}
return previous;

Выполнение →

Основная логика заключается в обходе списка до конца и применении такой логики, чтобы каждый узел был обратным, и в итоге мы получим обратный список

  1. создадим три временных узла, а именно
 current = head // which points to head 
 previous = null // which point to null 
 next = null // it also points to null

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

3. В цикле while для каждой итерации мы будем выполнять следующие операции

while (current  != null)  { 
    next = current.next; 
    current.next = previous; 
    previous = current; 
    current = next; 
}
  • сначала мы переходим к следующему узлу, указывая рядом с current.next
  • вторым шагом мы изменим текущую следующую ссылку на предыдущий узел, т.е. current.next = previous; сделав это, мы только изменим направление ссылки.
  • на третьем шаге мы сделаем предыдущий узел текущим, так как мы изменили направление ссылки, нам нужно двигаться вперед, делая текущий узел предыдущим.
  • на четвертом шаге мы действительно двигаемся вперед, делая следующий узел текущим.

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

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

4. Когда цикл while завершится, мы перевернем весь список, и наш последний предыдущий узел станет нашей новой головой, поэтому вернули его.

O/p : head → 11 → 1 → 8 → 10 → null

Код →

public ListNode reverse(ListNode head) {
    if (head == null) {
        return head;
    }

    ListNode current = head;
    ListNode previous = null;
    ListNode next = null;

    while (current != null) {
        next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

Счастливого кодинга :)

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?

20.08.2023 18:21

Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в 2023-2024 годах? Или это полная лажа?".

Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией

20.08.2023 17:46

В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.

Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox

19.08.2023 18:39

Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в частности, магию поплавков и гибкость flexbox.

Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest

19.08.2023 17:22

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

Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️

18.08.2023 20:33

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

Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL

14.08.2023 14:49

Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип предназначен для представления неделимого значения.