Approach

• 벡터 pal에 모든 노드들의 val값을 저장한다.
• 투 포인터로 처음과 끝을 지정하여 비교한다.
• val값이 다르면 false를 리턴. while문(투 포인트 값 다 동일)을 벗어나면 true

Code

/**
 * 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> pal;

        while(head)
        {
            pal.push_back(head->val);
            head = head->next;
        }

        int left = 0, right = pal.size()-1;

        while(left < right)
        {
            if(pal[left++] != pal[right--]) return false;
        }

        return true;
    }
};

Result

---

추가적인 해결방법 1

• node를 전역 변수로 설정하여 head와 연결시킨다.
• check함수는 먼저 head가 비어있으면 true를 반환한다.
• 비어있지 않다면 check함수에 head의 다음 리스트 노드를 입력하여 재귀 형식으로 만들어준다.
• 재귀형식으로 만들어주게 되면 head->next가 NULL일때까지, 즉 head의 끝부분까지 이동시킨 후 끝부분의 val과 현재 node의 val을 비교한다.

  class Solution {
  public:
      ListNode* node;
  
      bool check(ListNode* head)
      {
          if(!head) return true;
          bool respond = check(head->next) && (node->val == head->val);
          if(!respond) return respond;
          node = node->next;
          return respond;
      }
  
      bool isPalindrome(ListNode* head) {
          node = head;
  
          return check(head);
      }
  };

  

---

추가적인 해결방법 2

• slow, fast 투 포인트를 통해 비교한다.
• fast는 한번에 두 칸의 node를 이동시켜주고, slow는 한 칸의 node를 이동시켜준다.
• fast가 먼저 NULL에 도달하게되는데 이때 fast는 slow의 두 배가 된다.
• next 노드를 만들어 slow의 다음 next를 지정하고 slow->next노드는 reversed 노드를 지정한다. 그리고 reversed 노드는 slow로 바꿔주고 slow는 다시 next 노드로 바꿔준다.
• 위를 계속수행하면 slow는 head의 끝부분까지 오게되고 reversed는 head의 끝부분이 된다. 그리고 reversed->next의 값들은 이전의 slow 노드의 값으로 역순으로 가리키게 된다.

  class Solution {
  public:
      bool isPalindrome(ListNode* head) {
          if(head == NULL || head->next == NULL) return true;
  
          ListNode* reversed = NULL;
          ListNode* slow = head;
          ListNode* fast = head;
  
          while(fast != NULL && fast->next != NULL)
          {
              slow = slow->next;
              fast = fast->next->next;
          }
  
          while(slow != NULL)
          {
              ListNode* next = slow->next;
              slow->next = reversed;
              reversed = slow;
              slow = next;
          }
  
          while(reversed != NULL) {
              if(head->val != reversed->val) return false;
              head = head->next;
              reversed = reversed->next;
          }
  
          return true;
      }
  };