LeetCode 234. Palindrome Linked List

파이썬 알고리즘 인터뷰 문제 13번(리트코드 234번) Palindrome Linked List
https://leetcode.com/problems/palindrome-linked-list/

나의 풀이1

# 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

        temp = []
        curr = head
    
        while curr:
            temp.append(curr.val)
            curr = curr.next
        
        return temp == temp[::-1]

연결 리스트를 리스트로 바꾸어 푼 치사한 방법이다.

나의 풀이2

# 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:
        # 빈 리스트는 항상 palindrome
        if not head:
            return True

        # slow와 fast 포인터 초기화
        slow = fast = head
        curr = slow.next

        # 리스트 중간을 찾으면서 앞부분을 역순으로 변환
        while fast and fast.next:
            fast = fast.next.next  # fast는 두 칸씩 이동
            nxt = curr.next        # 다음 노드 저장
            curr.next = slow       # 현재 노드의 방향을 반대로 변경
            slow = curr            # slow를 한 칸 이동
            curr = nxt             # curr을 다음 노드로 이동

        # 리스트 길이가 홀수인지 확인하고 포인터 분리
        if fast:
            head1 = slow.next      # 중간 이후의 리스트 시작점
            head2 = curr          # 반대 방향 리스트 시작점
        else:
            head1 = slow.next
            head2 = slow
            head2.next = curr

        # 두 리스트를 비교하여 palindrome 여부 확인
        while head1 and head2:
            if head1.val != head2.val:
                return False
            head1 = head1.next
            head2 = head2.next

        return True

러너를 이용한 풀이다.
slow, fast를 동시에 출발시키면 slow가 중앙에 멈춘다.
slow를 진행하며 역순으로 바꾸고 두 리스트의 값을 차례대로 비교해본다.

다른 풀이

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        rev = None
        slow = fast = head
        # 런너를 이용해 역순 연결 리스트 구성
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next # 다중할당
        if fast:
            slow = slow.next

        # 팰린드롬 여부 확인
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        return not rev

마찬가지로 러너를 이용한 풀이지만, 코드가 훨씬 깔끔하고 우아하다.

배운 점

연결 리스트(Linked List)는 풀었더라도 코드의 우아함이 너무 차이 나는 경우가 있다.
다음은 흔한 유형, 자주 사용되는 방법이니 익숙해지자.

• head앞에 dummy로 None을 만들면 편한 경우
• 다중 할당을 이용하면 코드가 훨씬 깔끔해지는 경우
• slow, fast를 이용하기(1. 속도가 다른 경우) -> 중간 지점 찾기, 사이클 유무 따지기 등
• slow, fast를 이용하기(2. 출발 점이 경우) -> 뒤에서 n번째 찾기 등
• 뒤집기, 병합하기 유형

다중 할당이 헷갈렸다.
rev, rev.next, slow = slow, rev, slow.next과
rev.next, rev, slow = rev, slow, slow.next이 다르다.
왜그런지 궁금하다면 아래 글을 보자.

다중 할당에 대해 정리한 글
https://velog.io/@coding_study/파이썬의-다중-할당Multiple-Assignments