https://leetcode.com/problems/palindrome-linked-list/description/
Given the head of a singly linked list, return true if it is a
or false otherwise.
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Constraints:
- The number of nodes in the list is in the range [1, 105].
- 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
해당 문제를 Recursion / Data structure / Two pointer 어떤 걸로도 풀 수 있는 지를 물어보는 문제다.
1. C
가볍게 먼져 Data Structure로 풀어보았다. 굳이 Stack 까지도 필요 없이 array로 해결
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head) {
if(!head || !head->next) return true;
int arr[100000];
struct ListNode* temp = head;
int size = -1;
while(temp){
arr[++size] = temp->val;
temp = temp->next;
}
int i = 0;
while(i<size){
if(arr[i]!=arr[size]) return false;
else{
i++;
size--;
}
}
return true;
}
1-2. pointer로 풀어보자
다소 짜치는 여러 조건들을 나열해서 풀어봐야 한다 -_-;;
골자는 SLL Node의 중앙까지 pointer를 보내고 그 때까지 fisrt half 거를 reverse로 해준다.
그리고 총 node의 개수가 홀 or 짝수임에 따라서 pointer 세팅을 좀 해주고,
중앙으로부터 좌~우로 pointer를 옮겨가며 Palindrome check를 해준다.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head) {
if(!head || !head->next) return true;
struct ListNode *fast = head, *slow = head, *temp = NULL, *prev = NULL;
while(fast && fast->next){
fast = fast->next->next;
temp = slow->next;
slow->next = prev;
prev = slow;
slow = temp;
}
if(fast==NULL){//even number of nodes
while(slow){
if(prev->val != slow->val) return false;
prev = prev->next;
slow = slow->next;
}
return true;
}
else{//odd number of nodes
temp = slow->next;
while(temp){
if(prev->val != temp->val) return false;
prev = prev->next;
temp = temp->next;
}
return true;
}
}
2. Python
이번엔 잘 감은 안 잡히지만 해당문제를 Recursive하게 풀어보기로 한다.
솔직히 봐도 잘 모르겠다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
self.ptr = head
def recursive(node) :
if node :
if not recursive(node.next):
return False
if self.ptr.val != node.val:
return False
self.ptr = self.ptr.next
return True
return recursive(head)
뇌를 좀파먹는 느낌이 든다. Recursive!
아오 끝 없는 무한 loop에 빠지는 느낌 ㅠㅠ
3. C++
이것도 걍 Recursive하게 가보자.
Class 내부에서 ptr을 method 내부가 아닌 바깥에 공용? 변수로 선언하는 것이 kick!
/**
* 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:
ListNode*ptr;
bool recursive(ListNode* node){
if(node){
if(!recursive(node->next)) return false;
if(node->val != ptr->val) return false;
ptr = ptr->next;
}
return true;
}
bool isPalindrome(ListNode* head) {
ptr = head;
return recursive(head);
}
};