[leetcode 234] Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2 Output: false

Example 2:

Input: 1->2->2->1 Output: true

 

Follow up:
Could you do it in O(n) time and O(1) space?

 

문제 풀이:

첨에 follow up을 무시하고 풀었다. 어떻게 거꾸로 돌지?해서 무시함 ㅇㅇ

첫 번째 방법(c++):

연결리스트를 모두 벡터에 집어넣고 전체 길이가 홀수/짝수일때를 나눠서 가운데부터 비교한다.

/**
 * 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;
        
        ListNode* cur = head;
        
        while(cur != nullptr){
            v.push_back(cur->val);
            cur = cur->next;
        }
        
        int len = v.size();
        if(len == 0){
            return true;
        }
        
        int left, right;
        int mid = len/2;
        if(len % 2  == 1){
            left = mid-1;
            right = mid+1;
        }else {
            left = mid -1;
            right = mid;
        }
       
        while(left > -1 && right < len){
            if(v[left] != v[right]){
                return false;
            }
            left--; right++;
        }
        
        return true;
    }
};

 

두 번째 방법(java):

연결리스트를 거꾸로 순회한다.... 포인터 너무 어렵다

fast와 slow를 만들어서 fast는 slow의 두배 속도로 가도록 한다. 전체 연결리스트 길이가 홀수일 경우 순회했을 때 fast!=null && fast.next == null이고,  짝수면 fast==null이 된다.

prev는 왼쪽 리스트 순회, slow는 오른쪽 리스트를 순회한다. 연결리스트 길이가 홀수일 경우 slow가 한칸더 이동해야 한다. 

노드수가 홀 수 일때

 

 

 

 

 

 

 

노드 수가 짝 수 일때

 

 

 

 

 

 

 

 

reverse하기

이전 노드를 저장할 prev라는 노드를 만든다. 현재 노드(cur)의 next를 미리 저장해놓는다.

cur의 next에 prev를 연결한다. 이제 prev는 현재 노드를 가리키고 cur는 next를 가리킨다.

 

 

 

 

 

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode prev = null;
        ListNode fast = head;
        ListNode slow = head;
        
        while(fast != null && fast.next !=null){
            fast = fast.next.next;
            
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }
        
        if(fast != null){
            slow = slow.next;
        }
        
        while(prev!=null){
            if(prev.val != slow.val){
                return false;
            }
            prev = prev.next;
            slow = slow.next;
        }
        return true;
    }
    
}