LeetCode 234. 回文链表

朴灿烈づ我的快乐病毒、 2022-11-01 04:26 144阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//解法一：fast走两格,slow走一个,slow走的时候进行反转前半部分链表
    /**
     * 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;
            ListNode fast = head;
            ListNode pre = null;
            while(fast != null && fast.next != null){
        
                fast = fast.next.next;
                ListNode tmp = slow.next;
                slow.next = pre;
                pre = slow;
                slow = tmp;
            }
            if(fast != null)//长度为奇数fast会停在最后一个节点,slow此时是后半部分未反转的头节点，为了使得数量一致，slow需要后一一个节点
                slow = slow.next;
            while(pre != null && slow != null){
        
                if(pre.val != slow.val)
                    return false;
                slow = slow.next;
                pre = pre.next;
            }
            return true;
        }
    }

//解法二：花式递归 玩不懂。。。
    //https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
    class Solution {
        
        private ListNode frontPointer;
    
        private boolean recursivelyCheck(ListNode currentNode) {
        
            if (currentNode != null) {
        
                if (!recursivelyCheck(currentNode.next)) {
        
                    return false;
                }
                if (currentNode.val != frontPointer.val) {
        
                    return false;
                }
                frontPointer = frontPointer.next;
            }
            return true;
        }
    
        public boolean isPalindrome(ListNode head) {
        
            frontPointer = head;
            return recursivelyCheck(head);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/0da5fb05229d4d89ae1988b62b627c27.png