(Easy - Fast & Slow Pointers) Leetcode - 234. Palindrome Linked List

이 문제는 Linked-List가 주어졌을 때 이 리스트가 Palindrome인지 확인하는 문제입니다.

Palindrome이란 보통 'eye', 'madam', '다시합시다' 등과 같이 역순으로 읽어도 같은 말이나 구절 또는 숫자를 의미합니다.

이를 List에 대입하면 거꾸로 읽어도 같은 구조를 의미할 수 있습니다.

 

아주 간단하게 생각하면 리스트를 역순으로 하나 생성한 뒤 원래 리스트와 비교해 같은지 확인하는 방법이 있습니다.

하지만 조금 더 빠르게 할 수 있는 방법도 있습니다.

 

Palindrome은 역순으로 읽어도 같기 위해 반으로 나누었을때 뒤의 절반을 역순으로 만들면 앞의 절반과 뒤의 절반의 역순이 같습니다. 쉽게 생각해서 중간을 기준으로 반으로 접을때 같으면 Palindrom이라는 의미입니다.

 

그래서 Fast and Slow Pointers를 사용해 중간 노드를 찾습니다. 

역순 리스트를 만드는 방법은 두 가지가 있을 수 있습니다.

    1) 맨 처음 중간 노드를 찾는 과정에서 Slow 포인터를 활용해 역순 리스트를 동시에 만드는 방법

    2) 중간 노드를 찾은 이후에 중간 노드부터 리스트의 끝까지 역순 리스트로 만드는 방법

 

이렇게 역순 리스트를 만들어 비교해 Palindrome인지 확인해주면 됩니다.

1번 방식으로 역순 리스트를 만들면 slow 포인터부터 역순 리스트를 비교해주면 되고

2번 방식으로 만들었으면 head 포인터를 사용해 리스트를 비교해주면 됩니다.

 

저는 1번 방식으로 문제를 풀었습니다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        ListNode* rev = nullptr; // 역순 리스트
        while (fast && fast->next)
        {
        	// slow는 한 칸씩 중간까지 이동하므로 slow를 활용해 역순 리스트 생성
            ListNode* temp = new ListNode(slow->val, rev);
            rev = temp;

            slow = slow->next;
            fast = fast->next->next;
        }
		
        // 만약 리스트의 노드 수가 홀수라면 slow를 한 칸 더 이동
        if (fast) 
            slow = slow->next; 

		// 나머지 절반과 역순 리스트를 비교해 Palindrome인지 확인
        while (slow && rev) {
            if (slow->val != rev->val)
                return false;
            slow = slow->next;
            rev = rev->next;
        }

        return true;
    }
};