Java-программа для изменения связанного списка в зигзагообразном стиле

Опубликовано: 18 Сентября, 2022

Имея связанный список, измените его таким образом, чтобы преобразованный список имел форму a <b>c<d>e<f…, где a, b, c… — последовательные узлы данных связанного списка.

Примеры:

Input:  1->2->3->4
Output: 1->3->2->4 
Explanation: 1 and 3 should come first before 2 and 4 in
             zig-zag fashion, So resultant linked-list 
             will be 1->3->2->4. 

Input:  11->15->20->5->10
Output: 11->20->5->15->10

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

Простой подход для этого состоит в том, чтобы отсортировать связанный список, используя сортировку слиянием, а затем поменять местами альтернативу, но это требует временной сложности O (n Log n). Здесь n — количество элементов в связанном списке.

Эффективный подход , который требует O(n) времени, заключается в использовании одного сканирования, аналогичного пузырьковой сортировке, а затем в поддержании флага для представления того, какой порядок () мы находимся в настоящее время. Если текущие два элемента не в таком порядке, то поменяйте местами эти элементы, иначе нет. Пожалуйста, обратитесь к этому для подробного объяснения порядка замены.

Выход:

Given linked list 
4->3->7->8->6->2->1->NULL
Zig Zag Linked list 
3->7->4->8->2->6->1->NULL

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

Это также можно сделать рекурсивно. Идея осталась прежней, допустим, значение флага определяет условие, которое нам нужно проверить для сравнения текущего элемента. Таким образом, если флаг равен 0 (или false), текущий элемент должен быть меньше следующего, а если флаг равен 1 (или true), то текущий элемент должен быть больше следующего. Если нет, поменяйте местами значения узлов.

Выход:

11 ->15 ->20 ->5 ->10 ->
LL in zig zag fashion : 
11 ->20 ->5 ->15 ->10 ->

Анализ сложности:

  • Временная сложность: O(n).
    Обход списка выполняется только один раз, и он состоит из n элементов.
  • Вспомогательное пространство: O(n).
    O(n) дополнительного пространства из-за рекурсивного стека.

Пожалуйста, обратитесь к полной статье о реорганизации связанного списка в стиле зиг-заг для получения более подробной информации!

РЕКОМЕНДУЕМЫЕ СТАТЬИ