128일 (234. Palindrome Linked List) LinkedList, 리스트 조작
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, 10^5].
- 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
- 접근방법
시간복잡도는 O(n)으로 특히 공간복잡도를 O(1)에서 문제를 풀려면 주어진 연결리스트를 조작하여 푸는 방법 밖에 생각이 나지 않았다.
1. 먼저 연결리스트의 길이가 짝수인지 홀수인지 판별한다.
(1) 연결리스트가 1-2-3-4-5-6 (짝수) 라면?
→ mid는 1-2-3을 순차적으로 가리키며, end는 1-3-5를 순차적으로 가리키며 반복문이 종료된다.
mid는 3을 가리키므로 (123 / 456) mid = mid.next로 다음 노드인 4를 가리켜야한다.(123 / 456)
그래야 456에 해당하는 노드를 역순으로 조작하여 (123 / 654) 각각 (1,6) (2,5) (3,4)의 값을 비교하며 회문임을 판별한다.
(2) 연결리스트가 1-2-3-4-5 (홀수) 라면?
→ mid는 1-2-3을 순차적으로 가리키며, end는 1-3-5를 순차적으로 가리키며 반복문이 종료된다.
mid는 12345에서 3을 가리키므로, 345를 역순으로 조작하여 (543), 각 노드를 123과 비교하며 회문임을 판별한다.
2. mid의 위치부터 연결리스트를 역순으로 조작한다.
→ {1,2,5,2,1}이라면 head = {1,2,5}가 되며 reverseHead = {1,2,5}가 된다.
→ {1,2,5,4,3}이라면 head = {1,2,5}가 되며 reverseHead = {3,4,5}가 된다.
3. head와 reverseHead의 시작노드부터 끝까지 각 노드의 값을 비교하여 모두 같은 값이라면 true, 아니라면 false를 리턴.
- 코드
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode mid = head;
ListNode end = head;
ListNode reverseHead = null;
while(true) { // 1.
if(end.next != null && end.next.next == null) {
mid = mid.next;
break;
}
else if(end != null && end.next == null) break;
mid = mid.next;
end = end.next.next;
}
while(mid != null) { // 2.
ListNode nextNode = mid.next;
mid.next = reverseHead;
reverseHead = mid;
mid = nextNode;
}
while(head != null && reverseHead != null) { // 3.
if(head.val != reverseHead.val) return false;
head = head.next;
reverseHead = reverseHead.next;
}
return true;
}
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;
}
}
}
코드가 긴 것 같지만 접근방법 3개에 해당하는 반복문 3개를 구현하면 끝이다.
연결리스트의 길이가 짝수인가 홀수인가에 따라서 반절로 자른 후, 나머지 반절을 역순으로 연결하여 새로운 연결리스트를 만들고, 기존 연결리스트 반쪽과 비교하는 코드이다.
https://leetcode.com/problems/palindrome-linked-list/
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com