lt.234-回文链表

[案例需求]

[思路分析一, 简单突破]

• 经过近四十道链表题的锤炼, 笔主深刻的体会到, 链表题目跟集合, 指针真的是关联性太强了!!!
• 对于链表类的题目, 如果你在尝试遍历集合(无论是普通的遍历, 还是使用快慢针形式的) 有一定困难的话, 那么使用集合或者数组存储链表结点或者结点的值, 来解决给定问题, 是一种非常简单直接的方法;
• 比如这道题, 鉴定一条链表是否是回文链表, 我们直接遍历来比较的话, 肯定是稍微有点难想的, 那么可以把链表的结点拆下来, 题目要求顺序(因为要判断是否符合回文), 我们就让他顺序, 然后通过对撞双指针的形式比较即可.
• 选择数组的话, 可行, 但是你得遍历完链表才能知道结点个数, 进而才能去初始化数组, 再去遍历链表存储结点, 太繁琐!
• 我们就选择集合, 使用可以随机访问的集合, 那么肯定就list了
• 题目思路:
• 1. 遍历链表, 把链表值存入集合(直接把结点存入也是可行的)
• 2. 然后对撞双指针, 相向遍历list, 比较是否相等, 不相等, 直接返回false即可;

[代码实现一, ]

/** * 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) {
    
        //对于这种遍历难解决的问题, 我们大可以交给集合, 数组
        //全部放入数组(数组不知道大小, 干), 然后我双指针对撞遍历
        //那我就放进list, 然后对撞遍历
        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;
    }
}

[思路分析二, 快慢指针 ]

1. 找到前半部分链表的尾结点, 也就是整个链表中间结点的前一个结点, 先掌握求链表中间结点的写法吧: lt. 876. 链表的中间结点
2. 反转后半部分链表, lt. 206 反转链表
3. 判断是否回文
4. 恢复链表
5. 返回结果

/** * 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. 获取中间结点
        //2. 反转中间结点后面的链表
        //3. 从头指针和从中间结点往后遍历并比较
        //4. 恢复反转后的链表(再翻转一次)

        //1. 获取中间结点
        ListNode middleNode = getMiddleNode(head);

        //2. 反转中结点后面的链表
        ListNode behindMid = reverse(middleNode.next);

        //3. 连接起来
        //middleNode.next = behindMid;

        //4. 比较结点
        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;
    }

    //反转链表
    public ListNode reverse(ListNode head){
    
        //递归出口
        if(head == null || head.next == null)return head;

        //递归入口
        ListNode newHead = reverse(head.next);
        //归来
        head.next.next = head;
        head.next = null;

        return newHead;
    }
}

[思路分析三, 巧妙的解法, ]

• 题解参见: 点我

/** * 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;
    }
}

[思路分析三, 递归法]

// 待补充