Leetcode.com, задача №206. "Переворот связного списка".

!!НАШ БЛОГ ПЕРЕЕХАЛ!!

Мы создали свой сайт! Все материалы, опубликованные в этом блоге, переехали туда.

Наш новый сайт maddevelop.ru

А данную статью вы можете найти по ссылке

Условие

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

Пример

Входной список: 1 -> 2 -> 3 -> 4 -> 5 -> null

Выходной список: 5 -> 4 -> 3 -> 2 -> 1 -> null

Итеративный вариант решения

Немного теории.

Связный список — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.

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

public class ListNode
    {
        public int val;                     // поле, хранящее значение начала списка
        public ListNode next;               // поле, указывающее на всю последующую часть
        public ListNode(int x) { val = x; } // конструктор 
    }

Создать входной связный список из примера можно, например, так:

ListNode ssp = new ListNode(1);
ssp.next = new ListNode(2);
ssp.next.next = new ListNode(3);
ssp.next.next.next = new ListNode(4);
ssp.next.next.next.next = new ListNode(5);
ssp.next.next.next.next.next = null;

Итеративный подход (англ. iteration - «повторение») в разработке программного обеспечения — это выполнение работ параллельно с непрерывным анализом полученных результатов и корректировкой предыдущих этапов работы.

Код метода реверса связного списка:

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

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

• Запоминать ссылку на следующий узел.

ListNode nextTemp = curr.next;

• В текущем списке ссылку на следующий узел заменять на скорректированную.

curr.next = prev;

• Запоминать текущее состояние списка.

prev = curr;

• Переходить к следующему узлу.

curr = nextTemp;

Посмотрим, как работает алгоритм для связного списка 1 -> 2 -> 3 -> null.

Итерация №1

  nextTemp = curr.next = 2 -> 3 -> null
  curr.next = prev = null
  prev = curr = 1 -> null
  curr = 2 -> 3 -> null

Итерация №2

  nextTemp = curr.next = 3 -> null
  curr.next = prev = 1 -> null
  prev = curr = 2 -> 1 -> null
  curr = 3 -> null

Итерация №3

  nextTemp = curr.next = null
  curr.next = prev = 2 -> 1 -> null
  prev = curr = 3 -> 2 -> 1 -> null
  curr = null

Т.к. curr = = null, то произойдёт выход из цикла.

Временная сложность: n, т.к. количество итераций зависит от количества узлов списка.

Пространственная сложность: 1, т.к. мы используем лишь дополнительные переменные, кроме основного других циклов нет.

Рекурсивный вариант решения

Код решения с рекурсией выглядит таким образом:

  public static ListNode ReverseList(ListNode head)
  {
    if (head == null || head.next == null)
      retutn head;
    ListNode p = ReverseList(head.next);
    head.next.next = head;
    return p;        
  }

Рассмотрим действие алгоритма на примере списка 1 -> 2 -> 3 -> null.

Первый (основной) вызов метода
ReverseList(1 -> 2 -> 3 -> null)
{
  ListNode p = ReverseList(2 -> 3 -> null)
  Происходит второй вызов метода.
    ListNode p = ReverseList(3 -> null);
    Происходит третий вызов метода.
      Третий вызов возвращает 3 -> null, т.к. head.next == null.
    Получаем, что ListNode p = 3 -> null. 
    В начале второго вызова head = 2 -> 3 -> null.
    head.next.next = head
    Получаем, что head = 2 -> 3 -> 2 -> 3 -> null.
    При этом p = 3 -> 2 -> 3 -> null
        head.next = null
    Таким образом, head = 2 -> null, a p = 3 -> 2 -> null.
    Второй вызов возвращает 3 -> 2 -> null.
  При возврате к первому методу head = head -> head.next = 1 -> 2 -> null
  ListNode p = 3 -> 2 -> null.
  head.next.next = head = 1 -> 2 -> 1 -> 2 -> null
  При этом p = 3 -> 2 -> 1 -> 2 -> 1 -> 2 -> null 
  head.next = null = 1 -> null
  p, оно же и ответ, становится равным 3 -> 2 -> 1 -> null  
}

Временная сложность: n, по-прежнему зависит от длины списка.

Пространственная сложность: n, т.к. равняется глубине рекурсии.

Ещё больше интересной информации на нашем Telegram канале.