【必备算法】字符串（回文问题）：LeetCode题 9. 回文数，234. 回文链表

文章开头先放个传送门，是回文字符串相关的LeetCode题 字符串（回文问题）：LeetCode题 125. 验证回文串，680. 验证回文字符串 Ⅱ，647. 回文子串，5. 最长回文子串，两篇可以对比着看。

9. 回文数¹

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

解法一：转成回文串

• 思路：转换为字符串，然后问题变为字符串是否回文问题
• 复杂度
  • Time：O（n）
  • Space：O（n），需要额外一个字符串的空间

public boolean isPalindrome(int x) {
		// 数字转字符串直接 +“”
        String s = x + "";
        int i = 0, j = s.length() - 1;
        // 判断回文串模板
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++; j--;
        }
        return true;
    }

解法二：倒序比较

• 思路：那有没有一种不转为字符串的求法？有，求出当前数字逆序后的数值，然后比较（如123，逆序数为321），如果相等则回文。
• 复杂度
  • Time：O（n）
  • Space：O（1），数值操作，没有额外空间

public boolean isPalindrome(int x) {
        if (x < 0) return false;
        // 因为 x 后面还要比较，所以这里再拿一个变量保存
        int tmp = x;
        // 因为逆序后可能超出int范围如19999999999999
        long y = 0;
        while (tmp != 0) {
            // 1.求末位
            int num = tmp % 10;
            // 2.进位相加
            y = y * 10 + num;
            // 3.除10右移
            tmp = tmp / 10;
        }
        // 比较是否相同
        return x == y;
    }

234. 回文链表

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

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

解法一：栈

• 思路：遍历链表，将所有节点压入栈，再遍历一遍进行对比。这里切记，栈里应该存的是val，而不是ListNode，因为比较的时候顺序是相反的
• 复杂度
  • Time：O（n）
  • Space：O（n），用了个Stack

public boolean isPalindrome(ListNode head) {
        // 注：栈里存的是具体value
        Stack<Integer> stack = new Stack<>();
        // 注：链表用for遍历更简洁
        for (ListNode p = head; p != null; p = p.next) 
            stack.push(p.val);
        for (ListNode p = head; p != null; p = p.next)
            if (p.val != stack.pop())
                return false;
        return true;
    }

解法二：折半对比

• 思路：将链表前一半逆序，同时进行遍历比较。这里注意，若长度是奇数情况，则要将后面的指针（cur）后移一位
• 复杂度：
  • Time：O(n)
  • Space：O(1)

public boolean isPalindrome(ListNode head) {
        // 1.计算链表长度
        int len = 0;
        for (ListNode p = head; p != null; p = p.next) len++;
		
        // 2.将链表前一半倒序
        ListNode cur = head, pre = null;
        for (int i = 0; i < len / 2; i++) {
        	// 以下四步跟交换一样，都是模板套路
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
		
    	// 注：若长度是奇数，则要将cur后移一位再比较
        if (len % 2 == 1) cur = cur.next;
    	// 3.同时遍历前一半与后一半，比较val
        for (; pre != null && cur != null; pre = pre.next, cur = cur.next) 
            if (pre.val != cur.val)
                return false;

        return true;
    }