[C++] [LeetCode 234] Palindrome Linked List

---

문제 풀기 전 생각 : 

/*
listnode 형태로 들어오는 원소들을 vector 컨테이너에 넣어주고
앞과 뒤를 비교한다.
listnode 형태의 데이터를 다룰 수 있는지를 보는 문제인것 같다.
*/

---

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> v;
        for(ListNode *ln = head ; ln != NULL ; ln = ln->next){
            v.push_back(ln->val);

        }
        for(int i=0 ; i<v.size()/2 ; i++){
            if(v[i] != v[v.size() - 1 - i]) return false;
        }
        return true;
    }
};

https://leetcode.com/problems/palindrome-linked-list/

Palindrome Linked List - LeetCode

---

풀 때 어려웠던 점 또는 느낀점 :

어렵지 않게 금방 푼 문제였다.

링크드 리스트를 데이터 구조 수업에서 배운 덕분인것 같다.

---

개선방안 :

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head->next == nullptr) {
            return true;
        }
        
        ListNode *fast = head, *slow = head, *prev = nullptr;
        while (fast != nullptr && fast->next != nullptr) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        } // end of while-loop
        
        // Break the singly linked list.
        prev->next = nullptr;
        
        // Reverse the second list (referenced by slow).
        ListNode *newHead = nullptr;
        while (slow != nullptr) {
            ListNode *tmp = slow->next;
            slow->next = newHead;
            newHead = slow;
            slow = tmp;
        } // end of while-loop
       
        ListNode *list1 = head, *list2 = newHead;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val != list2->val) {
                return false;
            }
            list1 = list1->next;
            list2 = list2->next;
        } // end of while-loop
        
        return true;
    }
};

리스트를 반으로 자른후 뒤집고

비교하는 방식을 사용한것 같다.