234.回文链表

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表

如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路：将链表前半部分反转，和链表后半部分比较

package hot100;


/***
 * 回文链表
 */
public class huiwen {

    /**
     * 反转链表函数
     *
     * @param head 传入单链表
     * @return
     */
    public ListNode reverse(ListNode head) {
        //反转之后的链表
        ListNode dummy = null;
        //node指向传入的需要反转的链表
        ListNode node = head;
        while (node != null) {
            //next 保存下一个结点
            ListNode next = node.next;
            //node指向dummy
            node.next = dummy;
            //dummy向前移动 指向node
            dummy = node;
            //将node指向next
            node = next;
        }
        //将反转后的链表返回
        return dummy;
    }

    /**
     * 具体逻辑
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        //链表为空结点或者只有一个结点返回true
        if (head == null || head.next == null) {
            return true;
        }
        //用快慢指针找到链表中间结点
        ListNode slowNode = head;
        ListNode fastNode = head.next;
        while (fastNode.next != null && fastNode.next.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        //循环结束之后 slow到达链表中间结点[无论链表为奇数还是偶数]
        //循环结束之后 fast[奇数到达最后一个结点 这也就是后面为什么要分析奇数情况][偶数直接指向空结点]
        //slowSecond 支线链表后半部分的第一个结点
        ListNode slowSecond = slowNode.next;
        // 处理长度为奇数的情况 fast会停留在倒数第二个结点slowSecond应指向链表后半部分的第二个结点
        //例如：链表为 1 -> 2 -> 3 -> 2 -> 1，在fast和slow指针到达中间时，secondHalf应指向第二个2（即slow.next.next）
        if (fastNode.next != null) {
            slowSecond = slowNode.next.next;
        }
        //将链表的前半部分截断，确保链表的前后两部分分开
        slowNode.next = null;
        //判断两部分的连表是不是回文链表
        //1、第一部分 head被截断的前半部分: head
        //2、第二部分 slowSecond: 指向后半部分的第一个结点
        boolean isOrNot = equalsList(slowSecond, reverse(head));
        return isOrNot;
    }

    public boolean equalsList(ListNode nodeA, ListNode nodeB) {

        while (nodeA != null && nodeB != null) {
            if (nodeA.val == nodeB.val) {
                nodeA = nodeA.next;
                nodeB = nodeB.next;
            } else {
                return false;
            }
        }
        return true;

    }

}

时间复杂度 O(N)

空间复杂度O(1)