LCR 027. 回文链表

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

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

示例 1：

1->2->3->3->2->1

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

示例 2：

1->2

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

 提示：

• 链表 L 的长度范围为 [1, 105]

• 0 <= node.val <= 9

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

 注意：本题与主站 234 题相同：https://leetcode-cn.com/problems/palindrome-linked-list/

思路

• 字符串反转

• 数组统计+双指针判断

• 递归(巧妙之处在于先遍历至链表尾部，向前逐一遍历)

• 快慢指针

  • 避免使用 O(n) 额外空间的方法就是改变输入。

  • 我们可以将链表的前(或后)半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。

  • 该方法虽然可以将空间复杂度降到 O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

代码

• 字符串反转

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while(head!=null){
            sb.append(head.val);
            head = head.next;
        }
        return sb.toString().equals(sb.reverse().toString());
    }
}

• 数组统计+双指针判断

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        byte[] counts = new byte[100001];
        int index = 0;
        while (head != null) {
            counts[index++] = (byte) head.val;
            head = head.next;
        }
        int start = 0;
        int end = index - 1;
        while (start < end) {
            if (counts[start] != counts[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

• 递归

class Solution {
    private ListNode frontPointer;
    
    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return isPalindromeListNode(head);
    }

    private boolean isPalindromeListNode(ListNode cur) {
        if (cur != null) {
            if (!isPalindromeListNode(cur.next)) {
                return false;
            }
            if (cur.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }
}

• 快慢指针

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode p1 = head, p2 = head;
        ListNode n1 = null, o1 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            //记录前链表反转，该方法改变了原有链表结构
            o1.next = n1;
            n1 = o1;
            o1 = p1;
        }
        //处理节点数为奇数的情况
        if (p2 != null) {
            p1 = p1.next;
        }
        //对比前部分反转和后部分是否匹配
        while (n1 != null) {
            if (n1.val != p1.val) {
                return false;
            }
            p1 = p1.next;
            n1 = n1.next;
        }
        return true;
    }
}