List inversion (Three Implementations in Java)

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 code

Look 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 code

The 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 code

The 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 code

The 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

Blog post is the author originally in another platform, now migrated