Aunt Guan is participating in the “Java Theme month – Java brush question clocking”, see the activity link for more details

First of all, I want to clarify that every algorithm problem has multiple solutions, and we’ll just talk about a few excellent solutions in LeetCode ~, hopefully

Can help you, that we first look at the topic description ~

I. Title Description:

Determine if a linked list is palindromic. Example 1: Input: 1->2 Output: false Example 2: Input: 1->2-> 1 Output: true Advanced: Can you solve this problem with O(n) time complexity and O(1) space complexity?

Ii. Analysis of Ideas:

We can find that palindrome list which list on both ends of the corresponding position of the values are the same, so we can use the method of double pointer to compare on both ends of the element, and is moving towards the centre, but chain hold only one value in the table and a pointer to the next node, to get the value of the index of a particular position need time to O (N), and use an array to store an array list, We can access values anywhere in the list by indexing at O(1) time; So we can copy the value of the linked list into the arraylist and use the two-pointer method

Three, code implementation

public boolean isPalindrome(ListNode head) {
        // List is used here, using the list is ordered feature
        List<Integer> vals = new ArrayList<Integer>();
        // Copy the list values into the array
        ListNode currentNode = head;
        while(currentNode ! =null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // Use the double pointer to check whether palindrome
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if(! vals.get(front).equals(vals.get(back))) {return false;
            }
            front++;
            back--;
        }
        return true;
    }
Copy the code

Brush question summary

If you have other ideas to solve the problem, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, not just limited to the solution I said ha ~, excellent ideas and code is more learning significance, let’s work together