Реверс связанного списка в Java
В этом руководстве мы реализуем два алгоритма обращения связанных списков на Java.
2. Структура данных связанного списка****
Связный список — это линейная структура данных, в которой указатель в каждом элементе определяет порядок. Каждый элемент связанного списка содержит поле данных для хранения данных списка и поле указателя для указания на следующий элемент в последовательности. Кроме того, мы можем использовать головной указатель, чтобы указать на начальный элемент связанного списка:
После того, как мы реверсируем связанный список, заголовок будет указывать на последний элемент исходного связанного списка, а указатель каждого элемента будет указывать на предыдущий элемент исходного связанного списка:
В Java у нас есть класс LinkedList для реализации двусвязного списка, реализующего интерфейсы List и Deque . Однако в этом руководстве мы будем использовать общую структуру данных односвязного списка.
Давайте сначала начнем с класса ListNode для представления элемента связанного списка:
public class ListNode private int data; private ListNode next; ListNode(int data) this.data = data; this.next = null; > // standard getters and setters > Класс ListNode имеет два поля:
- Целочисленное значение для представления данных элемента
- Указатель/ссылка на следующий элемент
Связанный список может содержать несколько объектов ListNode . Например, мы можем создать приведенный выше пример связанного списка с циклом:
ListNode constructLinkedList() ListNode head = null; ListNode tail = null; for (int i = 1; i 5; i++) ListNode node = new ListNode(i); if (head == null) head = node; > else tail.setNext(node); > tail = node; > return head; > 3. Реализация итеративного алгоритма****
Давайте реализуем итерационный алгоритм на Java:
ListNode reverseList(ListNode head) ListNode previous = null; ListNode current = head; while (current != null) ListNode nextElement = current.getNext(); current.setNext(previous); previous = current; current = nextElement; > return previous; > В этом итеративном алгоритме мы используем две переменные ListNode , предыдущую и текущую , для представления двух соседних элементов в связанном списке. Для каждой итерации мы меняем эти два элемента местами, а затем переходим к следующим двум элементам.
В конце концов, текущий указатель будет нулевым, а предыдущий указатель будет последним элементом старого связанного списка. Таким образом, previous также является новым указателем головы обратно связанного списка, и мы возвращаем его из метода.
Мы можем проверить эту итеративную реализацию с помощью простого модульного теста:
@Test public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i 5; i++) assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); > LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseList(head); for (int i = 5; i >= 1; i--) assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); > > В этом модульном тесте мы сначала создадим пример связанного списка с пятью узлами. Кроме того, мы проверяем, что каждый узел в связанном списке содержит правильное значение данных. Затем мы вызываем итеративную функцию для обращения связанного списка. Наконец, мы проверяем перевернутый связанный список, чтобы убедиться, что данные перевернуты, как ожидалось.
4. Реализация рекурсивного алгоритма****
Теперь давайте реализуем рекурсивный алгоритм на Java:
ListNode reverseListRecursive(ListNode head) if (head == null) return null; > if (head.getNext() == null) return head; > ListNode node = reverseListRecursive(head.getNext()); head.getNext().setNext(head); head.setNext(null); return node; > В функции reverseListRecursive мы рекурсивно посещаем каждый элемент в связанном списке, пока не достигнем последнего. Этот последний элемент станет новым заголовком обратно связанного списка. Кроме того, мы добавляем посещенный элемент в конец частично перевернутого связанного списка.
Точно так же мы можем проверить эту рекурсивную реализацию с помощью простого модульного теста:
@Test public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i 5; i++) assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); > LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseListRecursive(head); for (int i = 5; i >= 1; i--) assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); > > 5. Вывод
В этом руководстве мы реализовали два алгоритма для реверсирования связанного списка. Как всегда, исходный код статьи доступен на GitHub .
С использованием стека «перевернуть» односвязный список
Доброго времени суток
Задача звучит как-то так:
С использованием стека «перевернуть» односвязный список строк (первый элемент
должен стать последним, 2-ой предпоследним и т.д.). Нужно реализовать
дополнительный метод в списке, который используя стек выполняет данную задачу,
модифицируя ссылки next в элементах списка (также необходимо поменять head и tail в
самом списке).
(*)Реализовать ту же самую задачу без использования структуры стек рекурсивно.
Реализовал стек и односвязный список, но не понимаю, как перевернуть его. Вернее теория понятна, но как это сделать на Node + разобраться с ссылками, мне непонятно.
Стэк
Кликните здесь для просмотра всего текста
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
import java.util.Iterator; public class MyStackT> implements IterableT> { private class Node { T value; Node next; Node(T value, Node onNextNode) { this.value = value; this.next = onNextNode; } } private Node head = null; private int count = 0; public void push(T value) { head = new Node(value, head); count++; } public T peek() throws Exception { if (head == null) { throw new Exception("Stack is empty!"); } return head.value; } public T pop() throws Exception { T result = peek(); head = head.next; count--; return result; } public int getCount() { return count; } @Override public IteratorT> iterator() { return new IteratorT>() { private Node curr = head; @Override public boolean hasNext() { return curr != null; } @Override public T next() { T res = curr.value; curr = curr.next; return res; } }; } }
Кликните здесь для просмотра всего текста
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
import java.util.Iterator; import java.util.NoSuchElementException; public class MyLinkedListT> implements IterableT> { private int size = 0; private Node head = null; private Node tail = null; public boolean checkEmpty() { return size == 0; } public int getSize() { return size; } public void addFirst(T value){ Node first=head; Node newNode=new Node(value,first); head=newNode; if(first == null){ tail=newNode; } size++; } public void addLast(T value){ Node newNode=new Node(value,null); if(head ==null){ head=tail=newNode; } Node curr=head; while (true){ if(curr == tail){ curr.next=newNode; tail=newNode; break; } curr=curr.next; } size++; } public void add(T value){ addLast(value); } public void removeFirst() throws Exception { checkEmpty(); head = head.next; if (head == null) { tail = null; } size--; } public void removeLast() throws Exception { checkEmpty(); if (size == 1) { head = tail = null; } else { for (Node curr = head; ; curr = curr.next) { if (curr.next.next == null) { tail = curr; tail.next = null; break; } } } size--; } public T getFirst(){ return checkEmpty() ? null : head.value; } public T getLast() { return checkEmpty() ? null : tail.value; } public T get(int index) return curr.value; } public Node getNodeAtIndex(int index) if (index 0 return curr; } //тот самый метод, непонятно, как это все сделать public void reverse() throws Exception { MyStackNode> myStack=new MyStack<>(); for(Node curr=head;curr != null ;curr=curr.next){ myStack.push(curr); } for(Node curr=null;myStack.getCount() != 0;curr=curr.next) { if(curr == null){ curr=myStack.pop(); curr=head; } curr=myStack.pop(); curr=tail; } } @Override public String toString() { if (size == 0) return ""; StringBuilder stringBuilder = new StringBuilder(); Node curr = head; do { stringBuilder.append(curr.value.toString()).append(','); curr = curr.next; } while (curr != null); return stringBuilder.toString(); } @Override public IteratorT> iterator() { class DoubleLinkedListIterator implements IteratorT> { Node curr; public DoubleLinkedListIterator(Node head) { curr = head; } @Override public boolean hasNext() { return curr != null; } @Override public T next() { T result = curr.value; curr = curr.next; return result; } } return new DoubleLinkedListIterator(head); } private class Node { T value; Node next; Node(T value, Node onNextNode) { this.value = value; this.next = onNextNode; } } }
В Java8 Как перемешать, перевернуть, копировать, повернуть и поменять местами список с помощью API-интерфейсов коллекции?
Фреймворк коллекции Java довольно удивителен. Класс коллекции состоит исключительно из статических методов, которые работают или возвращают коллекции.
Эти операции работают в списке различных коллекций , таких как List, Set и т.д. В этом уроке мы рассмотрим список коллекторских операций , которые мы будем выполнять в списке.
Давайте начнем:
Мы собираемся выполнить все эти операции: Shuffle (), Reverse (), Copy (), Rotate () и Swap ().
Сначала создайте класс CrunchifyJava8ShuffleList.java , Следующая вещь, чтобы создать List и с помощью Collection Framework выполнить все операции.
Пожалуйста, создайте ниже Java-класс в вашей среде Eclipse и запускайте как Java-приложение.
CrunchifyJava8ShuffleList.java
пакет crunchify. ком . учебник ;
импорт Java . Util. ArrayList ;
импорт Java . Util. Коллекции ;
импорт Java . Util. Список ;
* @author Crunchify.com
* Лучший способ перемешать, реверсировать, копировать, вращать и менять список в Java8
общественности учебный класс CrunchifyJava8ShuffleList <
общественности статический недействительным main ( Строка [ ] аргументы ) <
Список String > CrunchifyList знак равно новый ArrayList String > ( ) ;
CrunchifyList . добавить ( Google ) ;
CrunchifyList . добавить ( Facebook ) ;
CrunchifyList . добавить ( «Твиттер» ) ;
CrunchifyList . добавить ( «Snap Inc» ) ;
CrunchifyList . добавить ( Crunchify LLC ) ;
CrunchifyList . добавить ( TechCrunch ) ;
CrunchifyList . добавить ( «Verizon» ) ;
Список String > NewList знак равно новый ArrayList String > ( CrunchifyList ) ;
// Распечатать список перед любой операцией.
Система. вне. println ( «Результат печати перед любой операцией: / t» + CrunchifyList ) ;
// Произвольно переставляет указанный список, используя источник случайности по умолчанию.
Коллекции . shuffle ( CrunchifyList ) ;
Система. вне. println ( «Результат печати после shuffle (): / t» + CrunchifyList ) ;
// Меняет порядок элементов в указанном списке.
Коллекции . реверс ( CrunchifyList ) ;
Система. вне. println ( «Результат печати после реверса (): / t» + CrunchifyList ) ;
// Копирует все элементы из одного списка в другой.
Коллекции . копия ( newList , CrunchifyList ) ;
Система. вне. println ( «Результат печати после копирования (): / t / t» + newList ) ;
// Поворачивает элементы в указанном списке на указанное расстояние.
Коллекции . повернуть ( newList , 2 ) ;
Система. вне. println ( «Результат печати после rotate (): / t» + newList ) ;
// Возвращает количество элементов в этом списке.
Система. вне. println ( «Печать общего количества с использованием size (): / t» + newList . размер ( ) ) ;
// Меняет местами элементы в указанных позициях в указанном списке.
Коллекции . своп ( newList , 2 , 4 ) ;
Система. вне. println ( «Результат печати после swap (): / t / t» + newList ) ;
Выход консоли Eclipse:
Выход Eclipse Console
Результат печати перед любой операцией : [ Google , Facebook , Twitter , Snap Inc , Crunchify LLC , TechCrunch , Verizon ]
Результат печати после shuffle ( ) : [ Google , TechCrunch , Verizon , Facebook , Snap Inc , Twitter , Crunchify LLC ]
Результат печати после реверса ( ) : [ Crunchify LLC , Twitter , Snap Inc , Facebook , Verizon , TechCrunch , Google ]
Результат печати после копирования ( ) : [ Crunchify LLC , Twitter , Snap Inc , Facebook , Verizon , TechCrunch , Google ]
Результат печати после rotate ( ) : [ TechCrunch , Google , Crunchify LLC , Twitter , Snap Inc , Facebook , Verizon ]
Печать общего количества с использованием size ( ) : 7
Результат печати после замены ( ) : [ TechCrunch , Google , Snap Inc , Twitter , Crunchify LLC , Facebook , Verizon ]
Дайте мне знать, если вы хотите выполнить еще несколько операций и у вас есть любимый список действий в списке Java или наборе Java .
В Java8 Как перемешать, перевернуть, копировать, повернуть и поменять местами список с помощью API-интерфейсов коллекции?
ЧИТАТЬ ТАКЖЕ: Топ 10 ответов на вопросы об интервью на Java — обязательно прочитайте перед тем, как появиться на любом интервью с Java
перевернуть массив
Почему не выводится перевернутый массив? то есть, последний элемент массива должен стать первым и т.д.
public class Mane < public void sort(int[] massive)< int[]arraySort = new int[10]; for(int i = 4; i >= 0; i--) < arraySort[4 - i] = massive[i]; for(int a = 0; a < 5; a++)< massive[a] = arraySort[a]; >> > public static void main(String[] arg)< int[] mass = ; Mane m = new Mane(); m.sort(mass); for(int i: mass) < System.out.println(i); >> > Отслеживать
67.9k 216 216 золотых знаков 77 77 серебряных знаков 219 219 бронзовых знаков
задан 8 фев 2016 в 16:23
99 2 2 золотых знака 2 2 серебряных знака 8 8 бронзовых знаков
Вы дебажить пробовали?
8 фев 2016 в 16:24
я конечно не эксперт, но чет код слишком запутан.
8 фев 2016 в 16:25
4 ответа 4
Сортировка: Сброс на вариант по умолчанию
Зачем два массива, зачем вложенные циклы?
public void sort(int[] massive) < for (int i = 0; i < massive.length / 2; i++) < int tmp = massive[i]; massive[i] = massive[massive.length - i - 1]; massive[massive.length - i - 1] = tmp; >> Отслеживать
ответ дан 8 фев 2016 в 16:43
875 5 5 серебряных знаков 8 8 бронзовых знаков
Не знаю почему но у меня java.lang.ArithmeticException: divide by zero
11 фев 2017 в 2:47
@АндрейШпилевой где же вы там нашли деление на 0?
12 фев 2017 в 11:49
не я, а студия нашла
23 фев 2017 в 18:22
Спросите её тогда.
23 фев 2017 в 18:24
Collections.reverse(Arrays.asList(source)).toArray(new int[source.length]); да, это будет использовать избыточные ресурсы; нет, это не страшно
Отслеживать
ответ дан 8 фев 2016 в 16:47
36.1k 2 2 золотых знака 55 55 серебряных знаков 82 82 бронзовых знака
Обоснуйте фразу «нет, это не страшно». Вы случайно не разработчик Google Chrome?
8 фев 2016 в 17:09
Прикольно, но на примитивах не сработает, java.util.Collections.reverse ничего не возвращает, toArray(new int[whatever]) тоже работать не будет. ЗИС ИЗ ЖАВА!11
8 фев 2016 в 17:12
Кроме того, Arrays.asList создает представление над массивом, и вызовы set на этом списке меняют исходный массив, т.е. для Integer[] source = <1, 2, 3, 4, 5>; вызов Collections.reverse(Arrays.asList(source)) сделает перестановку в source .
8 фев 2016 в 17:15
@zRrr да, я попался на эту удочку, ответ писал параллельно болтая в офисе, позор мне.
8 фев 2016 в 19:04
Конечному пользователю все равно, сколько времени потрачено на код — ему главное, чтобы работало, и работало быстро. Ваш код: 1) не работает, 2) даже исправленный, создает ненужную копию массива в памяти. Если учить новичка, то зачем сразу плохому?