234. 回文链表

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

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

本题如果不用O(1）空间复杂度还是比较简单的，可以把链表转化为数组，然后双指针一个从前面一个从后面开始遍历，也可以用递归来做，都是用的O(N)空间复杂度，但是题目要求用O(1)，那就要费点心思了。

我这里给出的办法是将链表的一半给翻转，用头插翻转，然后逐一从前往后对比是否相同即可，那这么做的话，只需要额外的几个节点来记录一下临时变量，以及O(N/2)的时间复杂度，就是O(N)的时间复杂度。满足了题意。

代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {

        if (head == null) return true;
        ListNode fast = head.next;
        ListNode slow = head;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        //开始头插法
        ListNode r = slow.next;
        while (r != null && r.next != null){
            ListNode s = r.next;
            r.next = s.next;
            s.next = slow.next;
            slow.next = s;
        }
        slow = slow.next;
        while (slow != null){
            if (slow.val != head.val)
                return false;
            slow = slow.next;
            head = head.next;
        }   
        return true;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。