Palindrome linked list (copy linked list to array, speed pointer + reverse linked list)

Topic link ：https://leetcode-cn.com/problems/palindrome-linked-list/

subject ： Give you the head node of a single linked list head , Please judge whether the linked list is a palindrome linked list . If it is , return true ; otherwise , return false .

Method 1 ： Copy the linked list value to the array , Use double pointer to judge whether palindrome

Their thinking ：

The code is as follows ：

class Solution {
    
    public boolean isPalindrome(ListNode head) {
    
        List<Integer> list = new ArrayList<Integer>();// Create dynamic array 
        //  Copy the value of the linked list to the array 
        while(head != null){
    
            list.add(head.val);
            head = head.next;
        }

        //  Use double pointer to judge whether palindrome is true 
        int front = 0;
        int back = list.size()-1;
        while(front < back){
    
            if (!list.get(front).equals(list.get(back))) return false;// Basic palindrome judgment operation 
            front++;
            back--;
        }
        return true;
    }
}

Method 2 ： Speed pointer + Reverse a linked list

Their thinking ： Use the fast and slow pointer method to find the middle node of the linked list , Reverse the linked list of the second half of the node . Then traverse , Whether the corresponding values are equal .

public static boolean isPalindrome(ListNode head) {
    
        //  The first half is the tail node of the linked list ,half
        //  And reverse to half.next It is the linked list of the second half of the head node 
        ListNode half = findHalf(head);
        ListNode half_next = reverseList(half.next);

        // Next, judge whether to reply 
        ListNode p = head;
        ListNode q = half_next;
        boolean huiwen = true;
        while (huiwen && q != null){
    
            if (p.val != q.val) huiwen  = false;
            p = p.next;
            q = q.next;
        }

        // Remember to restore the linked list 
        half.next = reverseList(half_next);// General interviewers do not want to change the linked list structure , So go back 
        return huiwen;
    }
    public static ListNode reverseList(ListNode head){
    // Reverse the basic operation of the linked list 
    // Do not understand the reverse linked list iterative method https://blog.csdn.net/weixin_46184836/article/details/123512839
        ListNode pre = null;
        ListNode cur = head;
        ListNode next;
        while(cur != null){
    
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    public static ListNode findHalf(ListNode head){
    // When the fast pointer reaches the end , The slow pointer reaches the intermediate node 
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
    
            slow = slow.next;//slow The pointer goes one step at a time 
            fast = fast.next.next;//fast The pointer takes two steps at a time 
        }
        return slow;
    }