1. 문제 설명
정수 값을 가지는 노드로 이루어진 연결 리스트가 Palindrome인지 판별하는 문제입니다. 자세한 문제 설명은 문제 링크를 참조하세요.
2. 배열을 이용한 투 포인터 풀이
/**
* 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) {}
* };
*/
#include <array>
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* cur = head;
while (cur)
{
m_arr[m_size] = cur->val;
++m_size;
cur = cur->next;
}
int left = 0;
int right = m_size - 1;
while (left < right)
{
if (m_arr[left] != m_arr[right])
{
return false;
}
++left;
--right;
}
return true;
}
private:
std::array<int, 100'000> m_arr = {};
size_t m_size = 0;
};
C++
복사
가장 단순하게 떠올릴 수 있고 쉬운 풀이인 것 같습니다. 과정은 다음과 같습니다.
1.
연결 리스트를 순회하여 모든 값을 배열에 기록합니다.
2.
첫 번째 원소에서 오른쪽으로 이동하는 left 포인터와 마지막 원소에서 왼쪽으로 이동하는 right 포인터를 준비합니다.
3.
left와 right를 이동시키면서 가운데에서 만날 때까지 left와 right 값이 같은지 확인합니다. 한번이라도 다르면 Palindrome이 아니고, 가운데에서 만날 때까지 같다면 Palindrome입니다.
연결 리스트를 순회하므로 시간 복잡도는 O(n)이 되고, 사용하는 배열 크기는 고정돼 있으므로 O(1) 공간 복잡도가 됩니다.
3. 연결 리스트 절반을 거꾸로 뒤집어서 확인하는 풀이
/**
* 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) {
ListNode* slow = head;
ListNode* fast = head;
// slow를 리스트의 중간으로 이동, 짝수개면 길이/2 + 1까지 이동
while ((fast != nullptr) && (fast->next != nullptr))
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* rev = makeReverse(slow);
while (rev)
{
if (head->val != rev->val)
{
return false;
}
head = head->next;
rev = rev->next;
}
return true;
}
private:
ListNode* makeReverse(ListNode* head)
{
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur)
{
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};
C++
복사
리스트를 수정해야 하는 풀이입니다. 리스트나 포인터 연습하기엔 더 좋은 풀이입니다. 과정은 다음과 같습니다.
1.
노드 한 개씩 이동하는 slow 포인터, 노드 두 개씩 이동하는 fast 포인터를 준비합니다.
2.
slow와 fast로 이동시키다가 fast가 먼저 끝에 다다르면, slow 포인터는 가운데에 위치하게 됩니다.
3.
slow 포인터가 가리키는 노드 이후의 연결 리스트는 연결 방향을 모두 거꾸로 바꿉니다.
4.
연결 방향이 바뀌면, 마지막 노드부터 가운데 노드까지 순회할 수 있게 됩니다.
5.
첫 번째 노드를 가리키는 포인터와 마지막 노드를 가리키는 포인터를 가운데 노드까지 이동시키면서 두 포인터의 노드 값이 같은지 확인합니다.
6.
가운데 노드까지 값이 같으면 Palindrome, 한 번이라도 다르면 Palindrome이 아닙니다.
slow와 fast를 이용한 순회, 그리고 첫 번째 노드와 마지막 노드부터 시작하는 순회를 하므로 시간 복잡도는 O(n)입니다. 포인터만 사용하고 추가적인 메모리 할당을 하지 않으므로 O(1) 공간 복잡도가 됩니다.
