Palindrome Linked List

problem

주어진 링크드 리스트가 palindrome 인지 검사하는 문제입니다.

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

solution

//problem no : 234
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int count = 0;
        ListNode* prev = NULL; 
        ListNode* cur = head;
        ListNode* next = head->next;
        
        while(head){
            count++;
            head = head->next;
        }
        for(int i=0;i<(count+1)/2;i++){
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        } 
        
        if(count%2 == 1){
            prev = prev->next;
        }
        
        while(cur){
            if(cur->val != prev->val){
                return false;
            }
            cur = cur->next;
            prev = prev->next;
        }
        return true;
    }
};

코드 설명

1. 링크드 리스트의 크기를 구한다
2. 반절만큼 링크드 리스트를 뒤집으면서 이동한다.
3. 홀수면 prev를 한칸 더 이동한다.
4. <-prev cur-> 의 값을 비교하면서 이동한다!

후기

제가 생각한 알고리즘이 좋은 알고리즘이었던 것 같습니다.

그 와중에 fast(2칸씩) 와 slow(1칸씩)를 이용해서
제 코드처럼 링크드 리스트를 두번 돌지 않고,
한번에 절반을 구하면서, 뒤집는 것까지 하는 코드도 있더라구요.
보면서 괴물인가 싶었습니다. 하하...