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;
}

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

Шаблоны Angular PrimeNg
Шаблоны Angular PrimeNg

26.01.2023 14:14

Как привнести проверку типов в наши шаблоны Angular, использующие компоненты библиотеки PrimeNg, и настроить их отображение с помощью встроенной функции ngTemplateOutlet.

Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript
Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript

26.01.2023 13:19

Если вы веб-разработчик (или хотите им стать), то вы наверняка гик и вам нравятся "Звездные войны". А как бы вы хотели, чтобы фоном для вашего следующего сайта послужил начальный эпизод "Звездных войн"? 😁

Документирование API с помощью Swagger на Springboot
Документирование API с помощью Swagger на Springboot

26.01.2023 09:43

В предыдущей статье мы уже узнали, как создать Rest API с помощью Springboot и MySql .

Начала с розового дизайна
Начала с розового дизайна

25.01.2023 11:01

Pink Design - это система дизайна Appwrite с открытым исходным кодом для создания последовательных и многократно используемых пользовательских интерфейсов.

Шлюз в PHP
Шлюз в PHP

25.01.2023 10:51

API-шлюз (AG) - это сервер, который действует как единая точка входа для набора микросервисов.

14 Задание: Типы данных и структуры данных Python для DevOps
14 Задание: Типы данных и структуры данных Python для DevOps

25.01.2023 09:17

проверить тип данных используемой переменной, мы можем просто написать: your_variable=100