[LeetCode/릿코드] 234. Palindrome Linked List

[ 처음 풀이 ]

재귀함수를 이용해, input에서 주어지는 Linked List를 반대로 연결한 것을 구하고,

( 1->2->3->2->1의 Reverse라면 1<-2<-3<-2<-1)

구한 Reverse된 List와 원래 List를 Root Node부터 끝까지 항상 같은지 비교.

(중간 노드까지만 비교해도 되나, 중간 노드를 구하는 과정이 더 계산이 길어지는 것 같아 패스)

/**
 * 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 {
private:
    ListNode* tail = new ListNode();
    ListNode* startTail = tail;
    ListNode* getEnd(ListNode* head){
        ListNode* end = head;
        while(end->next != nullptr){
            end = end->next;
        }
        return end;
    }
    
    void getReverse(ListNode* head){
        ListNode* temp = getEnd(head);
        tail->val = temp->val;
        ListNode* tempHead = head;
        getReverse_(tempHead);
    }
    
    void getReverse_(ListNode* node){
        if(node->next != nullptr){
            ListNode* newNode = new ListNode(node->val);
            node = node->next;
            getReverse_(node);
            startTail->next = newNode;
            startTail = newNode;
        }
    }
    
public:
    bool isPalindrome(ListNode* head) {
        getReverse(head);
        while(head != nullptr){
            if(head->val == tail->val){
                head = head->next;
                tail = tail->next;
            } else {
                return false;
            }
        }
        return true;
    }
};