Everyone thinks of changing the world, but no one thinks of changing himself. 


Everyone thinks of changing the world, but no one thinks of changing himself.

Shanghai tap water comes from the sea, zhongshan zhuluo tea luo in the mountains. Very artistic conception of the sentence, reading backwards reading is the same meaning. Very good news for Chen, ocD patients. This paper shares three methods of judging palindromes based on single linked lists. All source code has been uploaded to Github: link

Based on the array

Array is used to store the value of the first half of the linked list, and fast and slow pointer method is used to intercept.

But this kind of array insertion in reverse order is time-consuming.

Tip: Always using Node.add (0,slow.data) is equivalent to inserting in reverse order

    private boolean isPalindromeByArray(Node node) {
        if (null == node || null == node.next) return true;
        List<Integer> nodeList = new ArrayList<>();
        Node fast = node;
        Node slow = node;
        nodeList.add(0, slow.data);
        while(null ! = fast.next && null ! = fast.next.next) { fast = fast.next.next; slow = slow.next; nodeList.add(0, slow.data); } Node curNode = slow;if(null ! = fast.next) { curNode = slow.next; } int index = 0;while(null ! = curNode) {if(curNode.data ! = nodeList.get(index)) {return false;
            }
            curNode = curNode.next;
            ++index;
        }
        return true;
    }Copy the code

Based on the stack

It’s the same idea as an array, but it’s stored in a stack, and then you keep going out of the stack and comparing it to the second half of the list. It’s more efficient.

    private boolean isPalindromeByStack(Node node) {
        if (null == node || null == node.next) return true;
        Stack<Integer> stack = new Stack<>();
        Node fast = node;
        Node slow = node;
        stack.push(slow.data);
        while(null ! = fast.next && null ! = fast.next.next) { fast = fast.next.next; slow = slow.next; stack.push(slow.data); }if(null ! = fast.next) { slow = slow.next; } Node curNode = slow;while(null ! = curNode) {if(curNode.data ! = stack.pop()) {return false;
            }
            curNode = curNode.next;
        }
        return true;
    }Copy the code

In situ linked list method

To realize palindromes without external storage, the idea of linked list inversion is used. Use the fast and slow pointer method to find the bottom half of the list, then reverse it and compare

    private boolean isPalindromeAuto(Node node) {
        if (null == node || null == node.next) return true;
        Node fast = node;
        Node slow = node;
        while(null ! = fast.next && null ! = fast.next.next) { fast = fast.next.next; slow = slow.next; } Node preNode = slow; Node firstNode = slow.next; Node curNode = slow.next.next; firstNode.next = null;while(null ! = curNode) { Node nextNode = curNode.next; curNode.next = preNode.next; preNode.next = curNode; curNode = nextNode; } slow = node; fast = preNode.next;while(null ! = fast) {if(fast.data ! = slow.data) {return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }Copy the code

The test results



end



Your likes and attention are my biggest support, thank you!