Palindrome 찾기 문제 (LinkedList)

                                    🤔 가운데 포인터를 둔다.

길이가 홀수인 경우 -> 가운데를 기준으로 좌,우 -+1 칸으로 포인터를 두기
길이가 짝수인 경우 -> 가운데를 비우고 생각하기

ex)

case1 odd [12221]
mid = 2
pointer 1 = mid - 1
pointer 2 = mid + 1

casw2 even [1221]
mid = 2
pointer 1 = mid-1
pointer 2 = mid

🗝️ python의 mid 포인터
python은 보통 / 또는 //(몫연산)을 통해서 mid를 체크한다.
짝수인 경우 = 중앙의 오른쪽 값 ex) 4 / 2 = 2
홀수인 경우 = 정중앙         ex) 5 / 2 = 2

✅ 매번 각 포인트를 한 칸씩 이동한다.
>>> 이동 후 값이 같은지 계속해서 비교하면 된다.
>>> pointer 1의 경우 첫번째 인덱스(=0)
>>> pointer 2의 경우 마지막 인덱스까지
반복한다.

✅ 하나라도 같지 않다면 false!

⌚ 시간 복잡도 : O(n)
🛰️ 공간 복잡도 : O(1)

                                    # Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        total = 0
        tmp = head

        while tmp != None:
            total += 1
            tmp = tmp.next

        mid = total // 2
        p1 = mid - 1
        if total % 2 == 0:
            # when even
            p2 = mid

        else:
            # when odd
            p2 = mid + 1

        while 1:
            if p1 < 0 and p2 > total - 1:
                break

            curr1 = head
            curr2 = head

            for i in range(p1):
                curr1 = curr1.next

            for i in range(p2):
                curr2 = curr2.next

            if curr1.val != curr2.val:
                return False

            p1 -= 1
            p2 += 1

        return True

                                    ✅ p1 = 0, p2 = last_idx

✅ p1 += 1, p2 -= 씩 감소시키자.

✅ 홀수, 짝수 구분
>>> [1,2,3,4]  p1 > p2 되는 시점에서 종료
>>> [1,2,3,4,5] p1 == p2 되는 시점에서 종료
>>> 🌟 p1 >= p2가 되는 시점에서 종료시키면 된다.
   >>> while로 변환하면 p1 < p2

                                    ✅ odd, even 둘다 mod-1에서 left가 끝난다.

✅ left를 reverse 시켜서 reverse 형태로 만든다.

✅ left_reversed 와 right를 각각 순회하여 모두 일치하는지 확인한다.

                                    ⌚ 시간: O(n)
🛰️ 공간: O(1)

                                    # Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """

        total_len = 0
        len_tmp = head

        while len_tmp != None:
            total_len += 1
            len_tmp = len_tmp.next

        mid = total_len // 2
        # left end = mid - 1

        # make left
        # [1,2,3(mid),4,5] mid = 2
        current = head
        prev = None
        right = None
        i = 0
        while i < mid:
            right = current.next
            current.next = prev
            prev = current
            current = right

            i += 1

        # prev = left
        # current = right

        # adjust right
        if total_len % 2 != 0: # when even
            current = current.next

        while prev and current:
            if prev.val != current.val:
                return False

            prev = prev.next
            current = current.next

        return True

                                    ❌❌❌ 오답 코드 ❌❌❌

// when? 좌-우를 분리할 때

        left_reversed = head
        prev = None
        for i in range(mid - 1):
            tmp_next = left_reversed.next
            left_reversed.next = prev
            prev = left_reversed
            left_reversed = tmp_next

        # right // mid = 3
        right = head
        print('head',)
        if mid % 2 == 0: #when even
            print('even right')
            for i in range(mid):
                if right == None:
                    print("right is None")
                    break
                right = right.next

                if right is not None:
                    print('i: ',i, 'right: ', right.val)
        else:
            # when odd
            print("odd right ")
            for i in range(mid + 1):
                right = right.next
        print("right, ", right)

                                    [1,2,3,4]와 [1,2,3,4,5]로 가정하자.

❌ mid는 전체 수가 짝,홀인지 구분하는 척도가 될 수 없다.
>>> 5 // 2 = 2 -> 짝수가 아니라 홀수이다

👉 Discovery!
>>> mid - 1은 항상 left end
>>> mid - odd 인 경우 정확히 중간
        - even인 경우는 right start

❌ right를 head로 초기화했다.
>>> left_reversed는 head와 같은 메모리를 사용한다.
    >>> 즉 포인터의 변경은 없지만(head), 내부 참조 값을 변경하면 실제로 바뀐다.

❌ 실제 right의 시작점 위치는 head가 아닌 left_reversed이다.
>>> 여기서 for문을 사용하면 처리가 어렵다는 것을 깨달았다.

case1. [1,2,3,4] mid = 2 (right)
>>> for사용시 left는 for i in range(mid - 1): # 1칸만 움직여야한다.
>>> 하지만 실제로 pointer를 변경해줘야 하는 노드는 1과 2이다.
>>> for문은 한번만 동작하기 때문에 1번만 변경되고, 2번은 반영되지 않는다.

>>> 실제로는 for i in range(mid)를 해줘야하는데, 이는 직관적인 계산을 어렵게 만든다.
    >>> 만약 적용한다면,
        >>> left(reverse)의 start = prev가 되고
        >>> right의 start = left_reversed가 된다.
            ❌ 작명의도와 맞지 않게 적용된다.

>>> while을 사용하는 것이 더 나으며,
변수명을 적절하게 변경해줘야 포인터 관리를 제대로 할 수 있있다.