회문 O (1) 추가 공간이는 # 234 Leetcode 문제입니다

Question

파이썬에서 목록을 링크 : 그것은 회문 인 경우 단일 연결 목록을 감안할 때

, 결정한다.

후속 조치 : O (n) 시간 및 O (1) 간격으로 수행 할 수 있습니까?

이 문제는 O (n) 공간으로 해결하기 쉽습니다. 그러나 O (1) 솔루션을 이해할 수는 없습니다. 내가 생각할 수있는 유일한 방법은 재귀를 사용하는 것입니다

이 작은 샘플 작동하지만 (최대 재귀 깊이가

사람은 O를 사용하여 솔루션을 제공 할 수 있습니다 초과

제공

# Definition for singly-linked list. 
# class ListNode(object): 
#  def __init__(self, x): 
#   self.val = x 
#   self.next = None 

class Solution(object): 
    current = None 

    def isPalindrome(self, head): 
     """ 
     :type head: ListNode 
     :rtype: bool 
     """ 
     if not head or not head.next: 
      return True 

     self.current = head 

     return self.compare(head) 

    def compare(self, head): 
     if not head: return True 

     if not self.compare(head.next): return False 

     if head.val != self.current.val: 
      return False 
     else: 
      self.current = self.current.next 
      return True 

1) 공간? 고맙습니다. 당신은 장소에 목록을 수정하도록 허용하는 경우

Answer 1

, 당신은 다음과 같은 작업을 수행 할 수

1. 으로 반복을 목록을 통해 얼마나 많은 요소 계산.
2. 두 번째로 반복하고 목록의 중간에서 시작하여 목록 노드의 포인터를 반대로하여 이전의 노드가 아닌 다음 노드를 가리 키도록합니다. 마지막 노드를 기억하십시오.
3. 이제 첫 번째 노드와 마지막 노드에 대한 포인터가 생기고 차이점을 발견하거나 중간에 도달 할 때까지 양쪽 끝에서 중간쪽으로 반복 할 수 있습니다.
4. 두 번째 반의 포인터를 반전시켜 원래 상태로 되돌립니다.

이것은 일정한 추가 공간 만 필요하며 선형 실행 시간이 있습니다.