(Leet Code c++)Palindrome Linked List

234. Palindrome Linked List

 

Given the head of a singly linked list, return true if it is a palindrome.

 

Example 1:

Input: head = [1,2,2,1] Output: true

Example 2:

Input: head = [1,2] Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

링크드 리스트로 이뤄진 수가 팰린드롬인지 확인해야 한다.

 

우선 링크드 리스트에 있는 수를 int형 벡터 v에 저장한다.

head를 이동하면서 v에 수를 저장.

 

front와 back 변수를 이용해 앞과 뒤의 수가 서로 같은지 확인하면서

front는 1씩 늘려주고, back은 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) {
        vector<int> v;
        int front = 0, back = 0;
        
        while(head != NULL){
            v.push_back(head->val);
            head = head->next;
        }
        
        back = v.size() - 1;
        
        while(front <= back){
            if(v[front] != v[back]){
                return false;
            }
            front++;
            back--;
        }
        
        return true;
    }
};