[LeetCode] #234. Palindrome Linked List (python)

문제

https://leetcode.com/problems/palindrome-linked-list/

Palindrome Linked List - LeetCode

주어진 연결리스트의 팰린드롬 여부를 확인하는 문제다.

 

예시 입출력

Input: head = [1,2,2,1]
Output: true

 

 

풀이

 

내 풀이

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        org=[]
        
        while (head is not None):
            org.append(head.val)
            head=head.next
            
        if org==org[::-1]:
            return True
        else:
            return False

연결리스트를 리스트로 변환한 후에 인덱싱을 활용해서 풀었다.

 

책 풀이

런너를 이용한 풀이

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

런너 기법은 연결리스트에서 투포인터를 사용하는 기법이다. 

런너 기법에는 빠른 런너, 느린 런너가 있다. 빠른 런너를 사용해서 중간, 길이 등을 판별할 수 있다.

빠른 런너는 2칸씩 이동하고 느린 런너는 1칸씩 이동한다. 느린 런너를 사용해서 처음~중간 지점까지의 역순 연결 리스트를 생성한다. 기존에 rev에 있던 값을 next가 가리키면서 처음 추가된 값이 맨 끝으로 가면서 역순 연결 리스트를 만드는 것이다.

slow가 중간까지 가면 fast는 없으니까 while문을 빠져나온다.

if fast 부분은 주어진 연결리스트가 짝수가 아닌 경우를 위해 slow를 한번 더 이동시켜준다.

그 이후에 팰린드롬 여부를 확인한다.

 

rev, rev.next, slow = slow, rev, slow.next

이 부분에서 코드가 실행되는 방식이 이해가 잘 안됐는데 파이썬의 다중할당 때문에 저 코드를 한줄로 실행하는 것과 하나씩 실행하는 것의 결과가 다르다.

 

파이썬은 =으로 변수에 값을 할당하는 것이 아니라 참조를 할당한다.

 

b는 a에 저장된 리스트를 참조하는 것이라서 a에서 값을 변경하면 b에서도 값이 바뀐다. 당연히 b에서도 값을 바꾸면 a가 보는 리스트의 값도 바뀐다. 둘이 같은 값을 가리키기 때문이다.

 

input으로 [1,2,2,1]이 들어왔을 때 풀이 코드가 실행되는 모습을 살펴보자.

rev=1→2→2→1, rev.next=none, slow=2→2→1 따라서 이 코드가 실행되고 나면

rev=1→none, slow=2→2→1이 된다.

이걸 한줄씩 실행하면 rev=slow를 하고 rev.next=rev를 하고 slow=slow.next를 하면 rev가 slow이기 때문에 rev=1→none이 되고 slow도 1→none이 된다.

그렇기 때문에 반드시 저 코드는 한줄에 작성해야 한다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰