题目

• 给定一个链表，判定它是否是回文链表
• 举例：1->2返回false 1->2->2->1返回true
• 时间复杂度O(n)空间复杂度O(1)

解析方法

• 如果没有时间复杂度为O(n)，空间复杂度O(1)的要求，那么这个解题方法很多，可以新建一个链表然后逆序比较两个链表是否相等即可得到结果，这样做时间复杂度O(n)空间复杂度O(n)
• 采用二分的方法，先找到中间节点截断然后将后半部分逆序，前半部分和后半部分对比，如果完全相同那么后半部分遍历后的指向是null此时表示这个链表是回文，如果后半部分指针不是null那么表示循环提前结束了也就不是回文链表。

源代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) slow = slow.next;//奇数需要走到下一个才是后半部分的开头
        slow = reverse(slow);//将后半段列表反转
        while (slow != null && slow.val == head.val) {
            slow = slow.next;
            head = head.next;
        }
        return slow == null;
    }
    
    //反转方法1头插法，开销比较大
    private ListNode reverse(ListNode head) {
        ListNode front = new ListNode(0);
        while (head != null) {
            ListNode temp = head;
            head = head.next;
            temp.next = front.next;
            front.next = temp;
        }
        return front.next;
    }
    //反转方法二
    private ListNode reverse1(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

代码分析

• 首先寻找中间节点所需时间是n/2,反转所需时间也是n/2，其次比较的时间也是需要n/2，所以整体时间是3n/2,所以时间复杂度是O(n),空间复杂度常数O(1)