01 링크 에서: 문자열 이 답장 문자열 인지 아 닌 지 어떻게 판단 합 니까?이 문자열 이 단일 링크 로 저장 되 어 있다 면?

사고: 문자열 이 답장 문자열 인지 아 닌 지 어떻게 판단 합 니까?이 문자열 이 단일 링크 로 저장 되 어 있다 면?
(1) 하나의 문자열 이 답문 문자열 인지 아 닌 지 를 어떻게 판단 합 니까? (알파벳 과 숫자 만 고려 하지만 문자열 에 다른 문자 가 포 함 될 수 있 습 니 다)
해법 1: 사고: 두 손가락 침 법
시간 복잡 도 o (n), 공간 복잡 도 o (1)
구체 적 인 코드 는 다음 과 같다.

class Solution {
    public boolean isPalindrome(String s) {
        int len = s.length();
        int left = 0;
        int right = len-1;
        while(left

(2) 이 문자열 이 단일 링크 로 저장 되 어 있다 면 (모든 문 자 를 고려)?
사고방식: 빠 르 고 느 린 손가락 침 법
(1) 느 린 바늘 은 한 걸음 씩 앞으로 가 고 빠 른 바늘 은 두 걸음 씩 앞으로 간다.
(2) 느 린 지침 이 앞으로 가 는 동시에 지침 의 방향 을 수정 하여 앞의 반 열 을 역방향 으로 한다.
(3) 전반 의 서열 과 후반 의 서열 이 같 는 지 비교 하면 된다.
알고리즘 시간 복잡 도 는 o (n) 이 고 공간 복잡 도 는 o (1) 이다.
구체 적 인 코드 는 다음 과 같다.

public class ListNode{
    char val;
    ListNode next;
    ListNode(char x){
        val = x;
    }
}

class Solution{
    public boolean isPalindrome(ListNode head){
        if(head==null||head.next==null){
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre =null;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            ListNode next = slow.next;//   slow      ,            
            slow.next = pre;          //    
            pre = slow;
            slow = next;
        }
        if(fast!=null){      //       
            slow = slow.next;   //     
        }
        while(slow!=null){
           if(slow.val != pre.val){         //          
               return false;
            }
            slow = slow.next;
            pre=pre.next;
            }
        }
        return true;
    }
}