[LeetCode] 234. Palindrome Linked List (O(n) 시간복잡도, O(1)공간복잡도 풀이)

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

Leetcode - Palindrome Linked List

문제 유형 : 연결 리스트

문제 난이도 : Easy

 

문제

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

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

 

단순 연결리스트의 head가 주어진다. 팰린드롬이면 true를, 아니라면 false를 반환하시오.

++: O(n)의 시간과 O(1)의 공간복잡도로 하실 수 있으시겠습니까?

 

풀이

그냥 따로 데이터를 저장하는 식으로 풀면 너무 쉬워지므로,
O(n)의 시간복잡도와 O(1)의 공간복잡도로 제한하고 풀기로 해봤다.

 

우선, 연결리스트의 크기를 알기 위해, 한 번 순차적으로 순회한다.

개수 n을 구한다.

그 뒤에는, 처음부터 n/2개의 노드를 뒤집는다.

next와 prev를 만들어서, next 포인터를 먼저 보내고, 현재 노드의 다음 노드를 prev로 하고, prev는 현재 노드 포인터로 이동, 현재 노드는 next포인터로 이동하는 식으로 한다.

 

뒤집는 작업을 n/2번 수행하면, n이 홀수인 경우는 다음과 같다:

[0,1,2,3,4](0 <- 1, 2 -> 3 -> 4)에서 prev = 1, node(현재) = 2, next = 2

짝수인 경우는

[0,1,2,3,4,5](0 <- 1 <- 2, 3 -> 4 -> 5)에서 prev = 2, node(현재) = 3, next = 3.

 

홀수인 경우, next를 한번 더 다음으로 보낸다. 
(위의 예시에서, next 를 3으로 보낸다)

그 뒤, prev와 next노드의 값을 비교하면서 계속 다음으로 보낸다. 맨 끝에 닿을 때까지.

중간에 값이 다른 경우가 있으면 false, 무사히 순회를 마치면 true를 반환한다.

 

코드

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) {
        int n = 0;

        auto node = head;
        while(node != NULL) {
            n++;
            node = node -> next;
        }
        node = head;

        if(n == 1) return true;

        auto next = node;
        ListNode* prev = NULL;
        for(int i = 0; i < n/2; i++) {
            next = node -> next;
            node -> next = prev;
            prev = node;
            node = next;
        }

        if(n%2) {
            next = next -> next;
        }

        while(prev != NULL && next != NULL) {
            if(prev -> val != next -> val) return false;
            prev = prev -> next;
            next = next -> next;
        }

        return true;
    }
};