234. 回文链表 Palindrome Linked List

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

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

解题思路

回文的意思就是从两端往中间走，每一个节点都是相同的，类似于一个镜像

数组双向遍历

利用数组下标，可以直接依次双向移动索引，逐一比较遍历，当索引相同（奇数元素数量）时或者 left > right（偶数元素数量） 则表示遍历结束








代码中用List来存放

public boolean isPalindrome(ListNode head) {
    List<Integer> valList = new ArrayList<Integer>();

    ListNode cur = head;
    while (cur != null) {
        valList.add(cur.val);
        cur = cur.next;
    }

    int left = 0;
    int right = valList.size() - 1;
    while (true) {
        if (left == right) {
            return true;
        }
        if (left > right) {
            return true;
        }
        if (valList.get(left) != valList.get(right)) {
            return false;
        }
        left++;
        right--;
    }
}

代码优化：

public boolean isPalindrome(ListNode head) {
    List<Integer> valList = new ArrayList<Integer>();

    ListNode cur = head;
    while (cur != null) {
        valList.add(cur.val);
        cur = cur.next;
    }

    int left = 0;
    int right = valList.size() - 1;
    while (left < right) {
        if (valList.get(left) != valList.get(right)) {
            return false;
        }
        left++;
        right--;
    }
     return true;
}

复杂度分析
时间复杂度：O(n)，其中 n 指的是链表的元素个数。
第一步： 遍历链表并将值复制到数组中，O(n)。
第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)。
总的时间复杂度：O(2n) = O(n)。
空间复杂度：O(n)，其中 n 指的是链表的元素个数，使用了一个数组列表存放链表的元素值。

进阶算法：快慢指针

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
如果需要将 O(n) 的空间复杂度变化为 O(1) ，那么就不能借用其他数据结构存储元素，只能利用指针

假设链表是下半部分的顺序，那么只需要依次比较 left 和 right 指向的结点值是否一致即可
什么是遍历终止条件？当 right 指向的结点的下一个结点是 null 时，或者 left 已经到达链表中部结点时，则遍历结束

那么算法问题转变为如下几个问题：
1.怎么反转链表后半部分结点
2.链表反转后，怎么让前半部分和后半部分同时遍历？

如果需要反转链表后半部分结点，需要先找到链表前半部分的最后一个结点

寻找链表前半部分的最后一个结点

假设链表的结点数量是偶数



假设链表的结点数量是偶数




当 fast 指针指向的结点的下一个结点或者下下一个结点是 null 时，此时 slow 指针指向的结点是前半部分最后一个结点

private ListNode endOfFrontHalf(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;
}

反转链表

反转链表可以参考 206 反转链表

private ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;

    while (cur != null) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }

    return pre;
}

快慢指针算法

public boolean isPalindrome(ListNode head) {
    // 找到前半部分链表最后一个结点
    ListNode endOfFrontHalf = this.endOfFrontHalf(head);
    // 反转后半部分链表，并且得到后半部分的第一个结点
    ListNode startOfBehindHalf = this.reverseList(endOfFrontHalf.next);

    ListNode left = head;
    ListNode right = startOfBehindHalf;
    boolean result = true;
    while (result && right != null) {
        if (left.val != right.val) {
            result = false;
        }
        left = left.next;
        right = right.next;
    }

    // 还原链表
    endOfFrontHalf.next = this.reverseList(startOfBehindHalf);
    return result;
}