剑指 Offer II 027. 回文链表

题目

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]
输出: true

示例 2：

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

提示：

• 链表 L 的长度范围为 [1, 105]
• 0 <= node.val <= 9

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

解题方法一

// 借助数组使用双指针判断
    public boolean isPalindrome(ListNode head) {
        List<Integer> arr = new ArrayList<>();
        ListNode curr = head;
        // 将链表全部节点存放到ArrayList
        while( curr != null){
            arr.add(curr.val);
            curr = curr.next;
        }
        // 创建数组两头指针
        int front = 0;
        int tail = arr.size() - 1;
        // 当两指针不重合
        while(front < tail){
            // 如果两指针指向元素不同则不符合回文返回false,否则返回true
            if(!arr.get(front).equals(arr.get(tail))){
                return false;
            }
            front++;
            tail--;
        }
        return true;
    }

解题方法二

// 借助栈结构进行判断  栈结构先进后出可以达到前后节点对应比较 need n extra space
    public static boolean isPalindrome1(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode cur = head;
        // 将链表所以节点依次压栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 遍历所有节点 并弹栈与节点相比较 如果有不同返回false
        while (head != null) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

解题方法三

// 借助栈结构进行判断 这次只需进行一半节点的比较 need n/2 extra space
    public static boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode first = head.next;
        ListNode cur = head;
        // 找中间节点
        while (cur.next != null && cur.next.next != null) {
            first = first.next;  // 依次走一步 最终结果指向中间节点
            cur = cur.next.next;  // 依次走两步
        }
        Stack<ListNode> stack = new Stack<ListNode>();
        // 将链表右半部分进行压栈
        while (first != null) {
            stack.push(first);
            first = first.next;
        }
        // 依次弹栈与链表前部分比较 相同为true
        while (!stack.isEmpty()) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

解题方法四进阶

// 使用有限几个变量空间复杂度为  O(1)
public static boolean isPalindrome3(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    ListNode n1 = head;
    ListNode n2 = head;
    // 找中间节点位置
    while (n2.next != null && n2.next.next != null) {
        n1 = n1.next; // 依次走一步 最终结果指向中间节点
        n2 = n2.next.next; // 依次走两步
    }
    n2 = n1.next; // n2 -> right part first node
    n1.next = null; // mid.next -> null
    ListNode n3 = null;
    while (n2 != null) { // right part convert
        n3 = n2.next; // n3 -> save next node
        n2.next = n1; // next of right node convert
        n1 = n2; // n1 move
        n2 = n3; // n2 move
    }
    n3 = n1; // n3 -> save last node
    n2 = head;// n2 -> left first node

    boolean res = true;
    while (n1 != null && n2 != null) { // check palindrome
        if (n1.val != n2.val) {
            res = false;
            break;
        }
        n1 = n1.next; // left to mid
        n2 = n2.next; // right to mid
    }
    n1 = n3.next;
    n3.next = null;
    while (n1 != null) { // recover list
        n2 = n1.next;
        n1.next = n3;
        n3 = n1;
        n1 = n2;
    }
    return res;
}