单向链表-对称链表

今天学习的算法是对称链表，今天这题真是有点跳转，反复提交了三次才通过。第一次错了后想了半小时实在没头绪，就看了下提示，发现需要用到之前做过的快慢指针和链表反转结合起来，这才恍然大悟。

题目介绍

对称链表就是给定一个单向链表，判断是不是对称的。我们用张图来表示下吧：

对称链表题目.png

实现思路

老规矩，先看解题思路图。

对称链表-解题.png

难点说明

首先将整个过程分为两大步：前半链表反转和前后链表比较。

1.前半链表反转，链表反转使用的技巧是之前实现过的：每次移动一位指针，然后把指向的节点交换到head位置。而为了让反转不超过中间节点，就需要使用到快慢指针（快的每次移动两步，这样只要快指针到了最后时就说明慢指针已经到中间位置了）。

2.前后链表比较：当快指针到了尾部后，这时前半段链表已经反转了，而且慢指针也到了中间位置。之后就只要继续移动慢指针，同时从head开始移动，比较慢指针和head指针的值是一样即可。

重点关注下边界情况，仔细分析

• 快指针指向节点不为null表示链表的长度为奇数，慢指针需要往后移动一位。
• 快指针指向节点为null表示链表的长度为偶数，慢指针不需移动。

实现代码

public boolean isPalindrome(ListNode head) {
    if (null == head || null == head.next) {
        return true;
    }
    //两个节点直接检查
    if (null == head.next.next) {
        return head.val == head.next.val;
    }

    ListNode quickNode = head.next.next;
    ListNode slowNode = head.next;
    ListNode slowPreNode = head;
    boolean isComparing = false;
    while (null != slowNode) {
        if(null != quickNode && null != quickNode.next){
        quickNode = quickNode.next.next;

        //链表反转
        slowPreNode.next = slowNode.next;
        slowNode.next = head;
        head = slowNode;
        slowNode = slowPreNode.next;
        }else{
        //首次交换
        if(!isComparing){
            //节点个数为奇数
            if (null != quickNode) {
            slowNode = slowNode.next;
            }
            isComparing = true;
        }

        if (head.val != slowNode.val) {
            return false;
        }
        head = head.next;
        slowNode = slowNode.next;
        }
    }
    return true;
}

感觉代码实现稍显复杂，后续去找找标准答案。