234. 回文链表问题

最近做了很多回文Palindrome问题，这里记录一下。

1. 回文整数

在这个之前，做了一个回文整数问题。对于回文整数问题，只需要注意3个点，

• 获取最高位

int val = 1;
while(x>0){
  x = x/val;
  val *= 10;
}

• 每次处理最高位和个位（最低位）
• 一次去除两位

就可以搞定。

2. 回文链表

解法1

最直接的来想，先把链表内容全部拿出来，拼成整数，再用上面的算法来做。

解法2

其实，对于回文问题，就是要反向比较，这对于 stack 非常适合。所以想着把链表所有元素都压入栈，然后将原始链表和出栈（即反序了）元素进行比较即可判断。

public boolean isPali(ListNode head){
        // 首先要有对于特殊情况的判断
        // if(==null) 之类的
        // 用 stack 来做
        Stack<Integer> stack = new Stack<>();
        ListNode flag = new ListNode(-1);
        flag.next = head;
        // 压栈完成
        while (flag.next!=null){
            stack.push(flag.next.val);
            flag.next = flag.next.next;
        }
        while (head!=null && !stack.isEmpty()){
            if(head.val!=stack.pop())
                return false;
            head = head.next;
        }
        return true;
    }

解法3

其实题目要求 O(n) 和 O(1)，所以解法2中其实不是很满足要求。这里我们考虑自己手动反转链表，再比较。就满足了 O(1) 的要求。
这里需要注意两个点：

• 如何获取中间位置
  这个是一个固定的方法，我们叫做双指针法获取中间位置。维护一个快的指针，一个慢的指针，每次快的动2个位置，慢的动1个，直到某一个指针越界了。
• 如何反转
  维护一个 prev链表，一个 next 链表，把 head.next 指向 prev，然后更新 head 和 next 直到越界即可

public boolean isPali2(ListNode head){
        // 用链表本身来做，这里有两个点，需要找中点，同时要反转链表。
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next.next!=null && slow.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 这个时候 slow.next 就是后半段链表的第一个
        ListNode half = reverse(slow.next);
        while (head!=null && half!=null){
            if(head.val!=half.val)
                return false;
            head = head.next;
            half = half.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head){
        ListNode prev = null;
        while (head!=null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;  //  这里的 Prev 就是原来链表的最后一个元素
    }