Часто встречается результат данных связанного списка.Вот реализация инверсии связанного списка в Java-коде.Существует три алгоритма, один рекурсивный, а другой нерекурсивный.
Во-первых, для удобства тестирования код рекурсивной реализации создания связанных списков вставлен в конец сообщения в блоге, чтобы читатели могли быстро приступить к тестированию.Предоставленный код можно скопировать и протестировать сразу после этого.
Давайте сначала посмотрим на узел Node.
public class Node {
//链表用于存储值
private final int value;
//指向下一个节点 理解为Node next更加恰当
private Node node;
public Node(int value) {
this.value = value;
this.node = null;
}
public int getValue() {
return value;
}
public Node getNode() {
return node;
}
public void setNode(Node node) {
this.node = node;
}
}
Взгляните на метод обратной рекурсии связанного списка
public Node reverserLinkedList(Node node){
if (node.getNode() == null || node == null){
return node;
}
Node newdata = reverserLinkedList(node.getNode());
node.getNode().setNode(node);
node.setNode(null);
return newdata;
}
//这个递归，返回值只是为了控制返回的是最后一个节点
//然后通过递归通过栈的特性，这里就是让它可以从最后一个节点开始把自己的子节点的子节点改成自己
//自己的子节点改为null
-
Реализация рекурсии всегда так проста. Краткий код является преимуществом рекурсии, а логика проста в обращении. Пока вы можете найти слой логики, а затем узнать специальные значения и выходы, рекурсия завершена.
-
Выход здесь, очевидно, if, чтобы найти последний узел, а затем можно начать рекурсивно реверсировать вперед, в то же время этот if может исключить случай, когда параметр имеет только один узел и параметр равен нулю.
-
Когда рекурсивный стек накопится до наивысшего уровня (суть рекурсии в стеке, каждая рекурсия кладется в стек, если работа этого слоя закончится, она выскочит и запустит следующий слой), после окончания last if, start to reverse, reverse Логика поворота на самом деле очень проста, пусть следующий узел текущего узла указывает на себя, а затем указывает на ноль
После разговора о рекурсивном алгоритме я также понимаю, что рекурсия на самом деле является стеком.Теперь мы используем ту же логику, но превращаем рекурсию в цикл, и используем структуру данных Stack, реализованную самой Java, для написания более эффективного кода.
public Node reverserLinkedList2(Node node){
Stack<Node> nodeStack = new Stack<>();
Node head = null;
//存入栈中，模拟递归开始的栈状态
while (node != null){
nodeStack.push(node);
node = node.getNode();
}
//特殊处理第一个栈顶元素（也就是反转前的最后一个元素，因为它位于最后，不需要反转，如果它参与下面的while，因为它的下一个节点为空，如果getNode()， 那么为空指针异常）
if ((!nodeStack.isEmpty())){
head = nodeStack.pop();
}
//排除以后就可以快乐的循环
while (!nodeStack.isEmpty()){
Node tempNode = nodeStack.pop();
tempNode.getNode().setNode(tempNode);
tempNode.setNode(null);
}
return head;
}
Логика ясна с первого взгляда, и объяснение выше очень ясно.
Существует также цикл, который проще написать, используя два указателя и не имея структуры стека.
public Node reverserLinkedList3(Node node){
//指向空，可以想象成位于第一个节点之前
Node newNode = null;
//指向第一个节点
Node curNode = node;
//循环中，使用第三变量事先保存curNode的后面一个节点
while (curNode != null){
Node tempNode = curNode.getNode();
//把curNode反向往前指
curNode.setNode(newNode);
//newNode向后移动
newNode = curNode;
//curNode 向后移动
curNode = tempNode;
}
return newNode;
}
Идея этого состоит в том, чтобы разделить связанный список на две части с помощью двух указателей, newNode — это перевернутая часть, curNode — перевернутая часть, а затем благодаря сотрудничеству двух указателей он продолжает двигаться вправо до тех пор, пока передний перевернуто
Теперь вставьте другие части кода, сначала вставьте конструкцию связанного списка.
public class LinkedListCreator {
//构建函数
public Node createLinkedList(List<Integer> list){
if (list.isEmpty()){
return null;
}
Node headNode = new Node(list.get(0));
Node tempNode = createLinkedList(list.subList(1, list.size()));
headNode.setNode(tempNode);
return headNode;
}
//测试方便的打印函数
public void printList(Node node){
while (node != null){
System.out.print(node.getValue());
System.out.print(" ");
node = node.getNode();
}
System.out.println();
}
}
основная функция
public static void main(String[] args) {
LinkedListCreator linkedListCreator = new LinkedListCreator();
Node node = linkedListCreator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5));
Node node2 = linkedListCreator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5));
Node node3 = linkedListCreator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5));
LinkedListReverser linkedListReverser = new LinkedListReverser();
Node res = linkedListReverser.reverserLinkedList(node);
Node res2 = linkedListReverser.reverserLinkedList2(node2);
Node res3 = linkedListReverser.reverserLinkedList3(node3);
linkedListCreator.printList(res);
linkedListCreator.printList(res2);
linkedListCreator.printList(res3);
}