NC+LC：判断字符串或链表回文结构

判断回文结构

NC141：判断回文

题目描述

题目地址

给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。

示例：输入： "absba" 返回值：true

解法1：转换为字符数组进行前后对比

import java.util.*;

public class Solution {
    public boolean judge (String str) {
        char[] ch = str.toCharArray(); //将字符串转换为字符数组
        int len = str.length();
        for(int i=0; i<len/2; i++){//对首尾对应元素判断是否相同
            if(ch[i] != ch[len-1-i]){
                return false;
            }
        }
        return true;
    }
}

解法2：利用首尾指针对字符串进行前后对比

import java.util.*;

public class Solution {
    public boolean judge (String str) {//使用首尾指针进行判断，空间复杂度为O（1）
        // write code here
        if(str == null || str.length() == 0)
            return false;
        int i = 0;//头指针
        int j = str.length() - 1;//尾指针
        while(i < j){
            if(str.charAt(i) != str.charAt(j))//判断指针所指元素是否相同
                return false;
            i++;
            j--;
        }
        return true;
    }
}

解法3：根据栈的先进后出进行判断

import java.util.*;

public class Solution {
    public boolean judge (String str) {//使用栈进行判断
        // write code here
        if(str == null || str.length() == 0)
            return false;
        char[] ch = str.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i<ch.length; i++){//先入栈
            stack.push(ch[i]);
        }
        for(int i = 0; i<ch.length; i++){//遍历判断字符元素是否与出栈元素一致
            if(ch[i] != stack.pop()){
                return false;
            }
        }
        return true;
    }
}

LC125：验证回文串

题目地址：https://leetcode-cn.com/problems/valid-palindrome/

示例：

输入: "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串

注意：与牛客网不同的是，LeetCode的该题只考虑字母和数字字符，增加了一些无关字符，不是单纯的判断

解法：双指针

可以先将无关字符去除，再进行判断，也可以直接在原字符串上进行判断
Character.isLetterOrDigit()方法可判断字符是否为字母或数字字符

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        while (left < right) {
            //遇到无关字符就移动指针
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                ++left;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                --right;
            }
            if (left < right) {
                //因为可以忽略字母的大小写，所以都转换为小写进行判断
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
}

NC96/LC234：判断一个链表是否为回文结构

题目地址：

NC96：判断一个链表是否为回文结构

LC：234.回文链表：https://leetcode-cn.com/problems/palindrome-linked-list/

示例：

输入：[1,2,2,1] 返回值：true 说明：1->2->2->1

解法1：使用栈

思路

先将链表的数值全部入栈，根据先进先出，出栈的顺序就为从后往前链表的顺序，所以遍历链表与出栈元素的值进行比较，出现不相等的值直接返回false，满足回文就返回true

实现代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    public boolean isPail (ListNode head) {
        // write code here
        if(head == null){
            return false;
        }
        ListNode pre = head;
        Stack<Integer> stack = new Stack<Integer>();
        while(head != null){//先入栈
            stack.push(head.val);
            head = head.next;
        }
        while(!stack.empty()){//再遍历判断出栈元素是否与节点值一致
            if(pre.val != stack.pop()){
                return false;
            }
            pre = pre.next;
        }
        return true;
    }
}

优化：快慢指针+栈

先利用快慢指针求中点，将后半部分进行入栈，然后遍历前半部分与出栈元素进行比较

    public boolean isPail (ListNode head) {
        // write code here
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null && fast.next.next!=null){//快慢指针求中点
            fast=fast.next.next;
            slow=slow.next;
        }
        Stack<ListNode> stack=new Stack<ListNode>();
        while(slow!=null){//将后半部分进行入栈
            stack.push(slow);
            slow=slow.next;
        }
        while(!stack.isEmpty()){//将出栈元素与前半部分元素进行对比
            if(stack.pop().val!=head.val){
                return false;
            }
            head=head.next;
        }
        return true;
    }

解法2：快慢指针+翻转

思路

先利用快慢指针求链表中点，将链表分为前后两部分，然后将后半部分进行翻转，最后将前后两部分从头开始遍历，判断对应元素是否相等
如链表1->2->3->2->1，分前后部分为1->2->3和2->1，将后半部分翻转为1->2，在两部分指向null之前进行元素判断

实现代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    public boolean isPail (ListNode head) {
        // write code here
        if(head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){//快慢指针求中点
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode reHead = reverseList(slow.next);//将后半部分进行翻转
        while(head != null && reHead != null){//前后部分进行遍历比较
            if(head.val != reHead.val){
                return false;
            }
            head = head.next;
            reHead = reHead.next;
        }
        return true;
    }
    public ListNode reverseList(ListNode head){//翻转链表
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}