[leetcode][Python]234. Palindrome Linked List(4일간의 팰린드롬 연결리스트 해결기🤪)

 

파이썬 알고리즘 인터뷰 8장이 시작되고 연결리스트 문제를 풀기시작했다.

 

 

첫문제인 만큼 어려운 문제는 아닐것이라 생각했는데

이게 왠걸 뭔말인지 잘 이해가 안갔다.

 

 

 

계속 책을 보면서 이해하려고 해봐도 내가 생각하는 이게 맞는건지 잘 이해가가지 않아 

https://github.com/onlybooks/algorithm-interview/issues/147

팰린드롬 연결리스트 질문 · Issue #147 · onlybooks/algorithm-interview

책의 저자에게 물어볼수있는 깃허브 이슈를 이용해 여쭤보았다.

 

 

 

결국 print를 이용해서 확인하고 이해하면 되는 문제였는데 괜히 시간도 오래 끌고 스트레스만 받은것같다.

처음에 출력할 수 있는 코드를 추가하였는데 에러가 발생하여 직접 linked list를 구현하여 만들어보기도하였는데

계속 에러가 발생했었다. 

그런데 그저 간단하게 print(fast, rev, slow) 를 이용해 확인하면 되는 것이었다. (창피하다)

 

 

---

하하하!

 

 

 def isPalindrome(self, head: Optional[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

 

정답코드는 4번의 우아한 풀이이다. 

 

내가 이해가 잘 되지않았던 코드는 

 

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

이 부분이다.

도대체 rev = slow가 되었는데 rev.next = rev가 어떻게 역순을 가리키는지 이해할 수가 없었다.

 

 

 

---

 

 

몇일을 생각해보니 조금은 이해가 되었고 print를 이용해 확인해보니 예측대로 출력되어 내 생각이 옳았음을 확인할 수 있었다. 

 

while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
            print(fast, rev, slow)

여기에 이렇게 print문을 추가하면 while문을 반복할 때마다 fast, rev, slow가 출력된다.

 

이렇게!!

 

head를 [1,2,3,2,1]로 넣었을 때 결과다. 

정리하면 이렇다.

 

1. fast = 3->2->1
   rev = 1 -> None
   slow = 2->3->2->1
2. fast = 1
   rev = 2-> 1 -> none
   slow = 3->2->1
3. fast = 1 # fast가 남아있어서 (홀수라서 slow = slow.next)
   rev = 2-> 1 -> none
   slow =2->1

 

깃허브 이슈를 통해 물어본 과정과 정확하게 일치했다.

 

 rev, rev.next, slow = slow, rev, slow.next 에서 

rev = slow를 통해 기존의 slow를 rev가 참조하게된다.

그리고 rev.next = rev를 이용해 기존의 rev를 rev.next가 참조하게된다.

그리고 slow는 slow.next를 참조하여 한칸 앞으로 가게 된다. 

이 일이 한줄으로 발생하기 때문에 앞에서 rev = slow를 한 일이 rev.next = rev에 영향을 끼치지않아 가능한것이다. 

 

 

내가 가장 이해가 안되었던 부분은 예를 들어 rev = 1-> None, slow = 2->3->1 같은 상황일 때

rev = slow이고 rev.next = rev라면  rev는 2->1->None -> 3-> 1 이 되는게 아닌지 였다.

그러나 출력결과를 확인하니 그렇지 않았다. 

연결리스트의 특성에 의해서 이런 결과가 나온것같다. rev.next가 rev(기존의 rev)를 참조하도록 하면

rev를 붙인 후 끝이다. 그 이후의 slow 뒷부분의 노드들은 잘려사라진다. 

 

 

이 다중할당이라는 작업이 동시에 일어나 한번의 트랜잭션으로 끝난다는 개념이

python에서 처음 접하는 개념이라 많이 헷갈렸다. 

 

 

 

 

이렇게 헤맨경험이 생겼으니 다음 연결리스트 문제는 수월하게 풀수있지않을까 기대해본다. 

이 문제를 구글링해보았을 때 연결리스트가 이처럼 무엇이 어떤 순서로 들었는지 나와있는 포스팅은 없어서 이해가 어려웠다.  나처럼 이해가 안되는 분이 계시다면 이 포스팅을 보고 이해하시기를 바란다!

 

 

 

 

 

 

 

질문 환영합니다. 

 

 

 

귀여운 파이리로 마음정화 

 

 

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."