연결된 목록이 있다고 가정합니다. 목록 요소가 회문을 형성하는지 여부를 확인해야 합니다. 따라서 목록 요소가 [5,4,3,4,5]와 같으면 이것은 회문이지만 [5,4,3,2,1]과 같은 목록은 회문이 아닙니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 빠름 :=헤드, 느림 :=헤드, rev :=없음 및 플래그 :=1
- 머리가 비어 있으면 true를 반환합니다.
- 단식과 다음 단식을 사용할 수 있는 동안
- 다음 단식을 사용할 수 있는 경우 플래그를 0으로 설정하고 루프를 끊습니다.
- 빠른 :=빠른 다음의 다음
- temp :=느림, 느림 :=다음으로 느림
- temp :=rev 및 rev :=temp의 다음
- 빠름 :=느림 다음, 느림 다음 :=rev
- 플래그가 설정되면 slow :=다음으로 느림
- 빠르고 느린 것은 None이 아니지만,
- 빠른 값이 느린 값과 같지 않으면 false를 반환합니다.
- 빠른 :=빠름 다음으로, 느림 :=느림으로
- 참을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class ListNode: def __init__(self, data, next = None): self.data = data self.next = next def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head class Solution(object): def isPalindrome(self, head): fast,slow = head,head rev = None flag = 1 if not head: return True while fast and fast.next: if not fast.next.next: flag = 0 break fast = fast.next.next temp = slow slow = slow.next temp.next = rev rev = temp fast = slow.next slow.next = rev if flag: slow = slow.next while fast and slow: if fast.data != slow.data: return False fast = fast.next slow = slow.next return True head = make_list([5,4,3,4,5]) ob1 = Solution() print(ob1.isPalindrome(head))
입력
[5,4,3,4,5]
출력
True