[LeetCode] 234. Palindrome Linked List, Easy

1. 문제

• 단일 연결 리스트가 주어질 때, 팰린드롬 리스트 여부를 반환하라.
• 팰린드롬 또는 회문 : 앞 뒤가 동일하게 구성되어 있는 것. madam, 12321 등등

2. 해결

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function isPalindrome(head: ListNode | null): boolean {
    
    let slow = head, faster = head;
    
    // 1. 중간 노드 찾기
    
    while(faster && faster.next) {
        slow = slow.next;
        faster = faster.next.next;
    }
    
    // 2. 후반부 뒤집기.
    let reverse = reverseList(slow);
    slow = head;
    
    // 3. 비교 
    while(reverse) {
       if(slow.val !== reverse.val) return false; 
        slow = slow.next;
        reverse = reverse.next;
    }
    
        
    return true;
    
};

function reverseList(head: ListNode | null) {
    
    let curr = head, prev = null;
    
    while(curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

• 팰린드롬 알고리즘이 별도로 있을 거 같기도하고 못풀겠어서 알고리즘을 정리했다.
• 원리는 리스트의 중간 노드를 찾고, 중간 노드를 기점으로 뒤에 있는 리스트를 뒤집은 다음 비교.