팰린드롬 연결리스트

김금동·2021년 10월 18일
0

알고리즘

목록 보기
2/12

문제 링크:https://leetcode.com/problems/palindrome-linked-list

저번보다는 단순하게 연결리스트가 팰린드롬인지만 확인하면 된다.(팰린드롬의 예: 토마토, 기러기, 요기요(광고아님))

rev = None
slow = fast = head

먼저 역순으로 만들기위해 rev = None 으로 역순의 씨앗을 심고
slow란 친구는 한발자국만 가게하고 (slow = slow.next)
fast란 친구는 두발자국씩 가게해서 (fast = fast.next.next)
fast가 골인하면 slow는 반만 가게 한다.
slow가 반을 왔을 때 이제까지 왔던길과 이제부터 가는 길을 비교하면 된다.

그래서 이제까지 왔던길과 가는 길이 똑같으면?
팰린드롬

아니면?
아닌거ㅇㅇ

while fast and fast.next:
    fast = fast.next.next
    rev, rev.next, slow = slow, rev, slow.next

rev에 이제까지 왔던길을 기록해주고
fast는 두발자국씩
slow는 한발자국씩 움직인다.

근데 fast가 while문을 끝내고 slow가 반을 왔을 때 정확하게 어딨을까?
연결리스트가 131이면 while이 1번 돌기때문에
fast는 뒷1에 와있고 slow는 3에 있고 rev는 1->None이다.
팰린드롬이 홀수개일때는 중간 숫자비교가 의미없기 때문에 slow를 한칸 더 움직여줘야한다.
연결리스트가 1331이면 while이 2번 돌기때문에
fast는 None이 되고 slow는 뒷3에 와있고 rev는 3->1->None이다.
따라서 짝수일때는 바로 비교해도 된다.

if fast:
    slow = slow.next

while slow:
    if rev.val == slow.val:
        rev, slow = rev.next, slow.next
    else:
        return False
return True

홀수개일때는 fast가 항상 존재한다. 그걸 이용해서 홀수개일때의 조건으로 사용해서 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 slow:
        if rev.val == slow.val:
            rev, slow = rev.next, slow.next
        else:
            return False
    return True

근데 사실 이 문제 때문에 포스팅한건 아니고

while fast and fast.next:
    fast = fast.next.next
    rev, rev.next, slow = slow, rev, slow.next

이 부분에서 왜 fast부터 시작하는 줄과 rev부터 시작하는 줄이 서로 바뀌면 안되는지 이해가 안갔어서 쓰게 됐다.

일단 두 줄을 바꿔서 풀면 값이 나오질 않는다.

그 이유는 무엇이 무엇을 참조하는지 보면 이해할 수 있다.

rev = None
slow = fast = head

이부분에서 slow와 fast는 문제에서 주어지는 연결리스트(head)를 참조한다.
근데 다중할당부분에서 rev = slow를 하여 rev또한 head를 참조하게 하여 rev.next = rev로 head를 rev로 변하게 했다.

그래서 두 줄을 바꾸면 fast는 rev로 변한 head를 참조하여 값이 완전하게 달라진다.

또한 저 다중할당부분을 테스트하면서 알게 된 사실은
다중할당의 순서 또한 제대로 고려해야한다는 것이었다.
예를 들어

a = [1,2,3]
b = [4,5]
b[0], b = 2, a
print(b) # [1,2,3]

a = [1,2,3]
b = [4,5]
b, b[0] = a, 2
print(b) # [2,2,3]

처음 부분의 b[0]의 b는 [4,5]를 참조하고
두번째 부분의 b[0]의 b는 다중할당 순서상 b가 a를 참조한 후이기 때문에 [1,2,3]을 참조한다.

while fast and fast.next:
    fast = fast.next.next
    rev, rev.next, slow = slow, rev, slow.next

그래서 rev, rev.next의 서순(왼쪽 오른쪽자리)은 바뀌면 안된다.
또한 slow도 밑으로 내려가면 바뀐 head를 참조하게 되어
반드시 같이 할당되어야 한다.

결국 rev가 head를 바꾸기 때문에 위식은 위아래로 바뀌면 안되고 rev할당의 서순이 바뀌면 rev가 참조하는게 달라져서 서순도 바뀌면 안되는 식이었다.(slow할당 서순은 바뀌어도 됨ㅇㅇ)

결론: 각각의 변수들이 뭘 참조하는지 정확하게 보자

profile
나원래chu해

0개의 댓글