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

古城微笑少年丶 2022-12-16 05:54 63阅读 0赞

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

## [9. 回文数¹][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. 回文链表][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;
        }

[LeetCode_ 125. _680. _ _647. _5.]: https://blog.csdn.net/weixin_43935927/article/details/109126387
[9.]: https://leetcode-cn.com/problems/palindrome-number/
[234.]: https://leetcode-cn.com/problems/palindrome-linked-list/