Переупорядочить связанный список в стиле зигзаг | Комплект-2

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

Примеры:

Ввод: 1-> 2-> 3-> 4
Выход: 1-> 3-> 2-> 4 

Ввод: 11-> 15-> 20-> 5-> 10
Вывод: 11-> 20-> 5-> 15-> 10

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

Идея состоит в том, чтобы пройти по заданному связанному списку и проверить, поддерживает ли текущий узел зигзагообразный порядок или нет. Чтобы проверить, поддерживает ли данный узел зигзагообразный порядок, используется переменная ind . Если ind = 0 , то данные текущего узла должны быть меньше данных его соседнего узла, а если ind = 1, то данные текущего узла должны быть больше данных его соседнего узла. Если текущий узел нарушает зигзагообразный порядок, то поменяйте местами оба узла. Для выполнения этого шага сохраните два указателя prev и next . prev сохраняет предыдущий узел текущего узла, а следующий сохраняет новый следующий узел текущего узла. Чтобы поменять местами оба узла, выполняются следующие шаги:

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

Ниже представлена реализация вышеуказанного подхода:

Сложность времени: O (N)
Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.