[2024] day 83. Leetcode 234. Palindrome Linked List

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 22일 (금)
Leetcode daily problem

234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/description/?envType=daily-question&envId=2024-03-22

Problem

연결형 리스트가 주어질 때, 해당 연결형 리스트가 팰린드롬 형태를 띄면 True, 아니면 False를 반환한다.
팰린드롬 : 앞으로 읽어도 뒤로 읽어도 같은 문자열

Solution

linked list

해당 문제는 주어진 연결 리스트가 팰린드롬 형태인지 확인하는 것이다.
head 노드를 시작으로 연결 리스트를 탐색하는데 해당 문제의 접근은
(1) 중간 노드를 확인
(2) 중간 노드 이후의 노드들을 역전시킴
(3) 역전시킨 중간노드가 처음부터 중간노드까지의 값과 같은지 확인
하면 되는 구조이다.

중간노드를 확인하는 과정은 포인터 2개를 활용해서 찾을 수 있다.
먼저 한 번에 한 칸 가는 slow, 한 번에 두 칸 이동하는 fast로 이동해
연결 리스트를 이동시켜나간다. fast 포인터가 연결 리스트에 끝까지 이동하면 slow에 있는 포인트가 해당 연결 리스트의 중간 노드에 지점에 속하게 된다.
그래서 투포인터를 사용해서 먼저 중간 노드를 찾는다.

그 이후에 slow 포인터로 중간 노드를 찾았기 때문에,
해당 중간 노드를 역전 시킨다.
빈 포인터를 하나 만들고 중간 노드를 업데이트 한다.

중간 노드를 역전 시킨 후에는 펠린드롬인지 확인하기 위해서 head와
연결형 리스트를 반으로 나눠서 중간 노드부터 끝까지의 노드를 역전시킨 노드의 값과 비교한다. 연결 리스트 두개를 포인터로 탐색하면서 하나라도 다르면 팰린드롬이 아니므로 False를 반환한다.
끝까지 탐색 했을 때 이상이 없으면 팰린드롬으로 판단하고 True를 반환한다.

Code

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev = None
        while slow:
            cur = slow
            slow = slow.next
            cur.next = prev
            prev = cur
        
        while prev:
            if prev.val != head.val:
                return False
            
            prev = prev.next
            head = head.next

        return True

Complexicity

시간 복잡도

연결 리스트의 중간 지점을 찾기 위해 느린 포인터와 빠른 포인터를 사용하여 한 번의 순회 할 때 O(n) 시간이 소요된다. 두 번째로 반을 나눈 연결형 리스트를 역순으로 뒤집는 과정에서 O(n) 시간이 소요된다.
두 번째 반을 역순으로 만든 후, 앞부분과 뒷부분의 노드 값을 비교할 때, 이 비교 과정도 O(n) 시간이 소요된다.
총 시간 복잡도는 O(n) 이다.

공간 복잡도

별도의 변수가 사용되지 않고, 주어진 연결 리스트의 노드들을 뒤집기 위해 연결 리스트의 구조를 변경하며 반복한다. 추가적인 공간을 필요로 하지 않고 반복문으로 계속 구현됐기 때문에 공간복잡도는 O(1)이다.

처음에는 한번 순회하면서 해당 노드의 값들을 리스트에 넣으면서,
연결 리스트의 길이를 체킹하고, 해당 길이의 반을 쪼개서 남은 리스트들을 리버스해서 비교했는데 time limit이 났다.
연결 리스트는 포인터를 사용해서 풀어야 하는 것 같다.