Головоломка
Учитывая неупорядоченный одиночный связанный список , предоставьте алгоритм для обращения такого связанного списка, используя только 2 указателя.
вход
Единый связанный список.
|
1
|
Example. 1 -> 4 -> 3 -> 2 -> 0 |
Выход
Перевернутый единый связанный список.
|
1
|
Example. 0 -> 5 -> 3 -> 2 -> 1 |
Решение с использованием Java в качестве языка программирования
Полная кодовая база распределена по 3 фрагментам Gist следующим образом
- Абстрактный класс, определяющий несортированный ADT связанного списка и реализующий банальные методы,
- Класс реализации, определяющий бизнес-логику для несортированного связанного списка,
- Тестовый класс, определяющий набор тестовых случаев для реализации ADT Unsorted Linked List.
Далее фрагмент кода, чтобы показать, как реализовать назначение с использованием итеративного подхода.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
|
public void iterativeReverse(){ if(head == null || head.next == null) return; Node p1 = head, p2 = p1.next, tmp = null; p1.next = null; while(p1 != p2) { // reverse links incrementally if(p2.next == null) { head = p2; tmp = null; } else tmp = p2.next; p2.next = p1; p1 = p2; if(tmp != null) p2 = tmp; }} |
Как развивается Алгоритм? Что ж, глядя на следующую диаграмму, все должно быть ясно.
Пересмотренный несортированный связанный список
Как интуитивно понятный, ту же проблему можно решить с помощью рекурсии; далее фрагмент кода, который показывает, как подходить к решению с помощью рекурсии.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public void recursiveReverse(){ if(head == null || head.next == null) return; Node p1 = head, p2 = p1.next; p1.next = null; _reverse(p1, p2); // reverse recursively}private void _reverse(Node p1, Node p2){ if(p2.next == null) { head = p2; p2.next = p1; p1 = p2; } else { Node tmp = p2.next; p2.next = p1; p1 = p2; p2 = tmp; _reverse(p1, p2); }} |
обсуждение
Основная идея заключается в постепенном изменении указателей. Как видно из предложенной схемы, два дополнительных указателя помогают при сканировании всего несортированного односвязного списка, и один указатель в момент выполнения операции инверсии. Исходя из кода, некоторые угловые случаи должны быть приняты во внимание; например, первая операция с указателем один (т. е. p1 на рисунке, когда он указывает на начало списка) должна аннулировать указатель на следующий по очевидным причинам: p2 будет указывать на p1, поэтому p1, указывающий на p2, будет создать петлю. С другой стороны, p2 нужно перемещать до тех пор, пока временный заполнитель не станет отличным от нуля: это создаст ситуацию, в которой в конце обработки p1 и p2 будут указывать на один и тот же хвостовой элемент. Такое условие (т. Е. P1 равно p2, что, в свою очередь, равно концу списка) представляет проверку завершения.
| Ссылка: | Кодирование: обращение неупорядоченного односвязного списка с использованием 2 указателей от нашего партнера по JCG Паоло Марески в блоге TheTechSolo . |