lt.234- Palindrome list

[ Case needs ]

[ Train of thought analysis 1 , Simple breakthrough ]

• After nearly 40 linked list questions , The writer deeply realized , Linked list title and set , Pointers are really too relevant !!!
• For the title of linked list class , If you're trying to traverse a collection ( Traversal is normal , Still use the form of fast and slow needles ) If there is some difficulty , Then use a set or array to store the values of linked list nodes or nodes , To solve a given problem , It's a very simple and direct method ;
• Like this one , Identify whether a linked list is a palindrome linked list , If we directly traverse to compare , It must be a little hard to think of , Then you can remove the nodes of the linked list , The order of the questions ( Because we have to judge whether it conforms to palindromes ), We'll just let him order , Then compare it in the form of colliding two pointers .
• If you select an array , feasible , But you have to traverse the linked list to know the number of nodes , Then we can initialize the array , Then traverse the linked list storage node , Too complicated !
• Let's choose the set , Use a collection that can be accessed randomly , Then it must be list 了
• Topic ideas :
• 1. Traversing the linked list , Store the linked list values into the set ( It is also feasible to store nodes directly )
• 2. Then hit the double pointer , Opposite traversal list, Comparison is equal , It's not equal , Go straight back to false that will do ;

[ Code implementation one , ]

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public boolean isPalindrome(ListNode head) {
    
        // For this kind of traversal difficult problem ,  We can give it to the collection ,  Array 
        // Put all into the array ( Array doesn't know size ,  dry ),  Then I double pointer collision traversal 
        // Then I'll put it in list,  Then collide 
        ListNode temp = head;

        List<Integer> list = new ArrayList<>();

        while(temp != null){
    
            list.add(temp.val);
            temp = temp.next;
        }

        //
        int size = list.size();

        for(int i = 0; i < size; i++){
    
            int left = i;
            int right = size - i - 1;

            if(list.get(left) != list.get(right)){
    
                return false;
            }
        }

        return true;
    }
}

[ Train of thought analysis II , Speed pointer ]

1. Find the tail node of the first half of the linked list , That is, the previous node of the middle node of the whole linked list , First master the writing method of finding the middle node of the linked list : lt. 876. The middle node of a list
2. Reverse the second half of linked list , lt. 206 Reverse a linked list
3. Judge whether palindrome or not
4. Restore the linked list
5. Return results

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public boolean isPalindrome(ListNode head) {
    
        //1.  Get the intermediate node 
        //2.  Reverse the linked list behind the intermediate node 
        //3.  Traverse from the beginning and back from the intermediate node and compare 
        //4.  Restore the inverted linked list ( Turn it over again )

        //1.  Get the intermediate node 
        ListNode middleNode = getMiddleNode(head);

        //2.  Reverse the linked list behind the node in 
        ListNode behindMid = reverse(middleNode.next);

        //3.  Connect 
        //middleNode.next = behindMid;

        //4.  Compare nodes 
        ListNode fromHead = head;
        ListNode fromMid = behindMid;
        
        boolean result = true;

        while(result && fromMid!= null){
    
            
            if(fromHead.val != fromMid.val) result = false;

            fromHead = fromHead.next;
            fromMid = fromMid.next;
        }

        return result;
    }

    public ListNode getMiddleNode(ListNode head){
    
        ListNode fast = head;
        ListNode slow = head;

        while(fast.next != null && fast.next.next != null){
    
           
                fast = fast.next.next;
                slow = slow.next;

        }

        return slow;
    }

    // Reverse a linked list 
    public ListNode reverse(ListNode head){
    
        // Recursive export 
        if(head == null || head.next == null)return head;

        // Recursive entry 
        ListNode newHead = reverse(head.next);
        // Return 
        head.next.next = head;
        head.next = null;

        return newHead;
    }
}

[ Train of thought Analysis III , Ingenious solution , ]

• See Synonyms at explanation : Am I

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
        public boolean isPalindrome(ListNode head) {
    
        if(head == null || head.next == null) {
    
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        while(fast != null && fast.next != null) {
    
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;
            prepre = pre;
        }
        if(fast != null) {
    
            slow = slow.next;
        }
        while(pre != null && slow != null) {
    
            if(pre.val != slow.val) {
    
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }
}

[ Train of thought Analysis III , Recursive method ]

//  To be added