Linked list this data results often met, here provides a linked list inversion Java code implementation, there are three algorithms, one is recursive, two non-recursive.
First of all, in order to facilitate the test, at the end of the blog post posted a recursive implementation of the linked list to create the code for readers to quickly start the test, the code provided can be copied later direct test
Let’s start with the Node Node
Public class Node {// List is used to store values private final int value; // Point to the next Node. public Node(int value) { this.value = value; this.node = null; } public intgetValue() {
return value;
}
public Node getNode() {
return node;
}
public void setNode(Node node) { this.node = node; }}Copy the codeLook at the linked list recursion method
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);
returnnewdata; } // This recursion is just to control that the last node is returned // and then passes through the stack recursively, so that it can start from the last node and change its child node to its own // its child node to nullCopy the code-
The implementation of recursion is always so simple, concise code is the benefit of recursion, and the logic is easy to deal with, as long as you can find a layer of logic, and then find a special value and exit, a recursion is done
-
The exit here is obviously the if, in order to find the last node, and then we can start the recursive inversion forward, and this if can exclude the case where there is only one node and the parameter is null.
-
Recursive stack the cumulative to the top (recursive nature is stack, each time the recursion in a stack, if the end of the run, will pop up, run the next layer), after the last if begin to reverse, reverse logic is very simple, let the next node of the current node points to yourself, and then point to null
Having said the algorithm of recursion, also understand that recursion is actually the Stack, now use the same logic, but turn recursion into a loop, using Java itself to implement the Stack data structure to write a more efficient code
public Node reverserLinkedList2(Node node){ Stack<Node> nodeStack = new Stack<>(); Node head = null; // Put it on the stack to simulate the state of the stack at the beginning of the recursionwhile(node ! = null){ nodeStack.push(node); node = node.getNode(); } // Special processing of the first top of the stack element (i.e. the last element before inversion, since it is at the end, no inversion is required if it participates in the followingwhileBecause its next node is null, if getNode(), then null pointer exception)if((! nodeStack.isEmpty())){ head = nodeStack.pop(); } // Eliminate the cycle of happiness laterwhile(! nodeStack.isEmpty()){ Node tempNode = nodeStack.pop(); tempNode.getNode().setNode(tempNode); tempNode.setNode(null); }return head;
}
Copy the codeThe logic is clear, and the explanation above is already clear
There is a simpler loop that uses two Pointers and does not require a stack structure
Public Node reverserLinkedList3(Node reverserLinkedList3){newNode = null; CurNode = Node; // In the loop, use the third variable to save the last node of the curNodewhile(curNode ! = null){ Node tempNode = curNode.getNode(); Curnode.setnode (newNode); // move newNode backwards newNode = curNode; // move curNode backwards curNode = tempNode; }return newNode;
}
Copy the codeThe idea is to divide a linked list into two parts. NewNode is the reversed part and curNode is the reversed part. Then, by combining the two Pointers, move the list to the right until the front part is reversed
Now post the rest of the code, first post the linked list building
Public class LinkedListCreator {// Build function 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);
returnheadNode; } // Test the convenient printing function public voidprintList(Node node){
while(node ! = null){ System.out.print(node.getValue()); System.out.print(""); node = node.getNode(); } System.out.println(); }}Copy the codeThe main function
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);
}
Copy the code