Прочтите это один раз, чтобы понять, графическое обращение односвязного списка

Java

предисловие

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

обратный связанный список leetcode исходный вопрос и ответ

Описание темы:Обратить односвязный список.

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

анализировать:

Предположим, есть связанный список 1 → 2 → 3 → Ø, мы хотим изменить его на Ø ← 1 ← 2 ← 3.

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

Код:

public ListNode reverseList(ListNode head) {  
    ListNode prev = null;   
    ListNode curr = head;   
    while (curr != null) {  
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

Реализация кода разворота графического связанного списка

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

public ListNode reverseList(ListNode head) {  //1
    ListNode prev = null;   // 2
    ListNode curr = head;   // 3
    while (curr != null) {   //4
        ListNode nextTemp = curr.next; //5
        curr.next = prev;  // 6 
        prev = curr;  //7
        curr = nextTemp; //8
    } 
    return prev;  //9
}

Схема первой строки кода

public ListNode reverseList(ListNode head) {  //1

Давайте последуем описанию заголовка, предполагая, что связанный список имеет 1, 2 и 3 элемента, за которыми следует нуль, и поскольку входными данными является заголовок ListNode, связанный список, который нужно перевернуть, выглядит следующим образом:

Иллюстрация второй строки кода

ListNode prev = null;   // 2

Присвойте null значению prev, то есть prev указывает на null, и получится следующая цифра:

Иллюстрация третьей строки кода

ListNode curr = head;

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

Диаграмма кода части контура

 while (curr != null) {   //4
        ListNode nextTemp = curr.next; //5
        curr.next = prev;  // 6 
        prev = curr;  //7
        curr = nextTemp; //8
    }

Петлевая частьСуть инверсии связанного спискаВ разделе давайте сначала пройдемся по циклу и проанализируем волну графически.

так какcurr указывает на голову,голова не нулевая, поэтому введите цикл.Сначала посмотрите на строку 5:

ListNode nextTemp = curr.next; //5

Присвойте curr.next переменной nextTemp, то есть nextTemp указывает на следующий узел curr (т. е. узел 2), и график выглядит следующим образом:

Затем выполните до строки 6:

curr.next = prev;  // 6

Присвойте prev значению curr.next, потому что инициализация prev указывает на null, то есть curr (узел 1) указывает на null, и диаграмма связанного списка выглядит так:

Затем мы видим выполнение до строки 7

 prev = curr;  //7

Присвойте curr значению prev, а prev указывает на curr.Схема выглядит следующим образом:

Далее мы выполняем до строки 8:

curr = nextTemp; //8

Назначьте nextTemp для curr, то есть curr указывает на nextTemp, как показано ниже:

На этом выполнение первого цикла завершено, и мы возвращаемся к условию цикла,curr все еще не равен нулю, мы продолжаем иллюстрировать это.

Снова выполняется 5-8 строк кода, и графики можно получить по очереди:

        ListNode nextTemp = curr.next; //5
        curr.next = prev;  // 6 
        prev = curr;  //7
        curr = nextTemp; //8

законченныйListNode nextTemp = curr.next;Задний:

законченныйcurr.next = prev;Задний:

законченныйprev = curr;Задний:

законченныйcurr = nextTemp;Задний:

Подойдите сюда, обнаружите, что curr все еще не равен нулю, вернитесь к циклу while и выполните его снова:

        ListNode nextTemp = curr.next; //5
        curr.next = prev;  // 6 
        prev = curr;  //7
        curr = nextTemp; //8

Рисунки доступны в последовательности:

Придя сюда, мы обнаруживаем, что curr уже равен нулю, и мы можем выйти из цикла. В это время prev указывает на обратную сторону связанного списка, поэтому после выполнения строки 9 реализуется функция обратного связанного списка:

 return prev;  //9

Ссылка и спасибо

Личный публичный аккаунт

  • Если вы хороший ребенок, который любит учиться, вы можете подписаться на мой официальный аккаунт, чтобы вместе учиться и обсуждать.
  • Если вы считаете, что в этой статье есть какие-либо неточности, вы можете прокомментировать или подписаться на мой официальный аккаунт, пообщаться со мной в частном порядке, и все смогут учиться и прогрессировать вместе.
Категории