Например, приведенный связанный список 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8, перестроенный список должен быть 1-> 3-> 5-> 7-> 2-> 4-> 6-> 8. Здесь все нечетные узлы (1,3,5,7) поддерживают свой относительный порядок и появляются перед всеми положением узлов (2,4,6,8), которые также поддерживают их порядок.
Ограничения ключей, которые делают эту проблему сложной задачей: < /p>
- Мы можем использовать только один стек в качестве дополнительного пространства (кроме O (1 ) переменные)
- Решение должно работать за один проход через связанный список
- Другие структуры данных не допускаются
- Оригинальный связанный список следует изменить на месте
< /li>
Значения узлов произвольны и не могут использоваться для идентификации позиции < /p>
< /li>
< /ol>
Я попытался Хранение ровных узлов в стеке при непосредственном связывании узлов, расположенных с нечетными, но у меня возникают проблемы с поддержанием правильных ссылок при реконструкции списка. Моя текущая реализация теряет некоторые соединения при попытке повторно переодеться узлами по установке из стека. Я особенно заинтересован в том, чтобы понять, как справиться с манипуляциями с указателями при приостановке узлов из стека при сохранении необходимого заказа. Чтобы переупорядочить узлы на основе их позиций. Задача состоит в том, чтобы переместить все нечетные узлы (1-й, 3-й, 5-й ...) перед всеми положением узлов (2-й, 4-й, 6-й ...), поддержание относительного порядка в каждой группе, используя только один стек, как Вспомогательное пространство. < /p>
Вот моя попытка реализации: < /p>Код: Выделить всё
class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; this.next = null; } } public class LinkedListRearranger { public ListNode rearrangeByPosition(ListNode head) { if (head == null || head.next == null) { return head; } Stack evenNodes = new Stack(); ListNode current = head; ListNode oddTail = null; int position = 1; // First pass: separate odd and even positioned nodes while (current != null) { ListNode nextNode = current.next; current.next = null; // Break existing link if (position % 2 == 1) { // Handle odd-positioned nodes if (oddTail == null) { oddTail = current; head = current; // Keep track of new head } else { oddTail.next = current; oddTail = current; } } else { // Push even-positioned nodes to stack evenNodes.push(current); } current = nextNode; position++; } // Second pass: reconnect even nodes from stack while (!evenNodes.isEmpty()) { oddTail.next = evenNodes.pop(); oddTail = oddTail.next; } return head; } } < /code> Ожидаемое поведение: для ввода списка: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 Ожидаемый вывод: 1 -> 3 -> 5 -> 7 -> 2 -> 4 -> 6 -> 8 < /p> Алгоритм должен: < /p> < P> обработать список в одном обходе, используя O (n/2) пространство стека для ровных узлов [*] Поддерживать относительное упорядочение нечетных узлов (1,3,5,7 ) < /p> < /li> Поддерживать относительный упорядочение ровных узлов (2,4,6,8) < /p> < /li> Правильно обрабатывать кромки, такие как списки с нечетной длиной [*] Избегайте создания каких -либо циклов в конечном списке < /li> < /ol> Фактическое поведение: моя реализация сталкивается с несколькими проблемами: < /p> < li> Некоторые узлы получают Потеряно во время перестройки < /p> < /li> Окончательный список иногда содержит неправильные соединения < /p> < /li> < li> При списках обработки с нечетной длиной, последний узел не обрабатывается должным образом < /p> < /li> В некоторых случаях список заканчивается с Cycles < /p> < /li> < /ol> Тестовый случай, который не сбои: < /p> ListNode head = new ListNode(1);Код: Выделить всё
head.next = new ListNode(2);Код: Выделить всё
head.next.next = new ListNode(3);Код: Выделить всё
head.next.next.next = new ListNode(4);Код: Выделить всё
head.next.next.next.next = new ListNode(5);
Ожидаемое: 1-> 3-> 5-> 2-> 4
Фактическое: Получение неверных соединений или потерянных узлов < /p>
Я подозреваю, что проблемы могут быть связаны с: < /p>
Неправильная обработка следующих указателей при разрыве и воссоединении узлы
< /li>
Не правильно отслеживать хвост списка узлов с нечетными узлами < /p>
< /li>
Крайные случаи, которые я не рассматривал в операциях стека
[*] Использование фиктивного узла головки для упрощения обработки первого узла
Различные подходы к разрыву и повторному соединению
< /li>
Поддержание отдельной ссылки для списка ровных узлов < /p>
< /li>
< /ol>
Но Каждая попытка либо нарушает требование о сложности пространства, либо не может поддерживать правильный заказ узла. < /p>
Что я делаю не так в моей реализации? Как я могу решить эти проблемы при сохранении ограничений сложности пространства и обеспечивая правильные соединения узлов?
Подробнее здесь: https://stackoverflow.com/questions/794 ... ngle-stack
