[1스4코2파] # 159. LeetCode Pattern 234. Palindrome Linked List

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (159차)
[4코1파] 2023.01.13~ (151일차)
[1스4코1파] 2023.04.12~ (62일차)
[1스4코2파] 2023.05.03 ~ (41일차)

Today :

2023.06.11 [159일차]
LeetCode Patterns
234. Palindrome Linked List
https://leetcode.com/problems/palindrome-linked-list/

234. Palindrome Linked List

문제 설명

singly linked list가 주어졌을 때, 해당 리스트 원소들이 Palindrom 조건에 해당하면 Ture, 그렇지 않다면 False를 return함 !

Palindrome은 회문 또는 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열

문제 풀이 방법

Palindrom 은 LIFO(Last in First Out) 구조로 stack을 이용하면 된다. 일단 singly linked list를 돌면서 stack 이라는 리스트에 넣었고, 그 후에 리스트를 reverse 해서 값이 같으면 Palindrom 이니까 True, 아니면 False로 처리했다. 굿

Time O(N), space O(N)

내 코드

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

        while head.next:
            stack.append(head.val)
            head = head.next
        stack.append(head.val)
        return True if stack[:] == stack[::-1] else False

증빙

여담

톱밥 문제 ㅋ

나는 공간, 시간 Complex 를 O(N) 으로 했는데
다른 풀이 보니까 Recursion을 사용해서

# 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.left = ListNode(0, head)

        def recursiveFun(head):
            if not head:
                return True
            
            right = recursiveFun(head.next)
            self.left = self.left.next
            return right and self.left.val == head.val

        return recursiveFun(head)

이런식으로 recursion의 two pointer를 이용해서 비교하는 방법도 있음
이것도 time O(N), space O(N)임

여기서 나아가서 space O(1) 으로 짜려면 two point에 middle을 찾아서 비교해서 풀면 space가 좀 효율적이게 짜짐

# 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:
        if not head:
            return True

        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