https://leetcode.com/problems/palindrome-linked-list/
Problem
연결 리스트가 팰린드롬 구조인지 true/false를 반환해라.
input = [1,2,2,1]
output = true
전략 1 : 스택을 이용한 풀이
팰린드롬을 판별하기 위해서는 앞 뒤로 판별 가능한 자료구조로 풀이를 진행할 수 있다. 그 중 스택 자료구조로 먼저 연결리스트를 스택에 복사해 넣은 다음, 다시 연결리스트를 앞에서부터 이동하면서 값을 조회하고 , 스택은 pop()을 호출하며 뒤에서 부터 값을 빼고 비교하는 식으로 풀이가 가능하다.
public boolean isPalindrome(ListNode head) {
Stack<Integer> st = new Stack<>();
ListNode node = head;
while (node != null) {
st.add(node.val);
node = node.next;
}
while (head != null) {
if (head.val != st.pop()) {
return false;
}
head = head.next;
}
return true;
}
하지만 스택 자료형은 스레드 안전성 문제 때문에 더이상 쓰이지 않는다. 그래서 다음 풀이와 같은 전략을 사용한다.
전략 2 : Deque를 이용한 풀이
아까 스택 풀이같은경우 연결리스트를 모두 넣고 다시 모두 빼면서 비교하는 식으로 진행했다. 이 자료형은 앞을 빼지 못하지만 이번 Deque를 활용한 풀이는 앞 뒤를 같이 빼면서 런타임 시간을 좀 더 줄일 수 있다.
Deque는 인터페이스 이며, 구현체는 LinkedList와 ArrayDeque가 있다. 이중 앞 뒤를 뺄 때 시간 복잡도가 O(1)인 LinkedList를 구현체로 사용하면 된다.
public boolean isPalindrome(ListNode head) {
Deque<Integer> deque = new LinkedList<>();
ListNode node = head;
while (node != null) {
deque.add(node.val);
node = node.next;
}
// 데크가 모두 비거나(짝수개수) 1개 이하(홀수 개일때)가 될때까지 비교
while(!deque.isEmpty() && deque.size()>1){
if(deque.pollFirst() != deque.pollLast()){
return false;
}
}
return true;
}
전략 3 : 러너 기법을 활용한 풀이
아무런 자료 구조를 사용하지 않고 단지 러너 기법을 활용하면 런타임 시간이 더 짧게 풀이를 할 수 있다. 이는 팰린드롬 연결리스트 문제의 제대로 된 풀이법이라 한다.
러너기법이란, 연결리스트를 순회할 때 2개의 포인터를 동시에 사용한다. 한 포인터가 다른 포인터보다 앞서게 한다. 빠른 러너는 두 칸씩 건너뛰고 느린 러너는 한 칸씩 이동시킨다. 이때 빠른 러너가 연결리스트의 끝에 도달하면 느린러너는 연결리스트의 중간 지점을 가르키게 된다. 이 같은 방식을 사용하여 중간 위치를 찾아내면 전체 길이를 알아낼 수 있고, 여기서 부터 값을 비교하거나 뒤집기를 시도할 수 있는 연결리스트의 대표적 풀이 기법이다.
다음은 러너 기법을 사용해서 뒤집기를 시도하는 풀이이다.
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
// 홀수 개 일때 느린 러너가 한 칸 더 앞으로 가도록 처리
if (fast != null){
slow = slow.next;
}
// 중간에 도달한 느린 러너를 기준으로 하여 역순 연결리스트를 만든다.
ListNode rev = null;
while(slow != null){
ListNode next = slow.next;
slow.next = rev;
rev = slow;
slow = next;
}
while(rev != null){
if(rev.val != head.val)
return false;
rev = rev.next;
head = head.next;
}
return true;
}
Fast 러너는 Slow러너가 연결리스트의 중간까지 오는 데 도와주는 도구일 뿐이다.
그리고나서 홀수 개임을 빠른 러너가 판단하고 느린 러너를 한칸 더 앞으로 이동하도록 처리한다. 다음 중간 러너를 통해 역순의 연결리스트를 새롭게 만든다. 다음은 while문이 한 사이클 지날때마다 변화된 그림이다.
자료구조를 사용하지 않으니 정말 빠르다.
레퍼런스
'Algorithm > Leetcode' 카테고리의 다른 글
[LeetCode 23] Merge K Sorted Lists - 우선순위 큐 (1) | 2024.02.05 |
---|---|
[Leetcode 2] Add Two Numbers - 전가산기,연결리스트 (0) | 2024.01.12 |
[Leetcode 42] Trapping Rain Water - 투 포인터 (1) | 2023.12.26 |
[Leetcode 1] Two Sum - 4가지 방식의 풀이 (1) | 2023.12.24 |
[Leetcode 5] Longest Palindromic Substring - 투 포인터+슬라이딩윈도우 (0) | 2023.12.21 |