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

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