2.6 회문

문제

주어진 연결리스트가 회문(Palindrome)인지 검사하는 함수를 작성해라.

 

해법

1. 뒤집어서 비교하기

연결리스트를 뒤집어서 비교해서 같으면 그 연결리스트는 회문이며, 비교는 반절만 하면된다.

def get_reverse(node):
    reverse_head = None
    while node is not None:
        n = Node(node.data)
        n.next = reverse_head
        reverse_head = n
        node = node.next
    return reverse_head

def isEqual(n1, n2):
    while n1 is not None and n2 is not None :
        if n1.data != n2.data :
            return false
        n1 , n2 = n1.next , n2.next
    return n1 is None and n2 is None

def Solution(node):
    return isEqual(node, get_reverse(node))

 

2. Stack과 Runner pointer를 이용한 순환적 접근법

runner pointer(fast pointer)를 이용하여 중간지점을 알아내고, 그동안 왼쪽부터 하나씩(slow pointer) 데이터를 stack에 넣는다. 

중간지점부터는 stack에서 데이터를 꺼내서 현재 pointer의 data 와 비교한다. 

def Solution(node):
    fast , slow = node , node
    stack = []
    while fast is not None and fast.next is not None:
        stack.append(slow.data)
        fast = fast.next.next
        slow = slow.next

    if fast is not None:
        slow = slow.next
    while slow is not None:
        if stack.pop() != slow.data :
            return false
        slow = slow.next
    return True

3. 재귀적으로 접근하기

재귀적으로 가장 끝까지 가서 뒤에서 부터 회문의 오른쪽 부분을 가지고 있도록 하고, 전체 길이를 알아낸다. 

코드상에서 전체길이는 list의 길이 +1 ( 2로 나누었을때 홀수는 전체길이/2 의 위치가 중간점이고 짝수인경우 전체길이/2보다 작은 부분이 항상 회문의 왼쪽 부분이 되기 떄문에, 그렇게 처리하기 위해 전체길이를 list의 길이 +1로 들고있는다) 

재귀에서 돌아오는 것은 뒤에서부터 처리를 하기 때문에 현재 인덱스가 중심보다 오른쪽인 경우에는 새로만든 구조체에서 현재위치를 저장함으로써 현재위치보다 오른쪽 리스트를 순환할 수 있도록 포인터를 들고있는다. 

현재인덱스가 중심보다 왼쪽인 경우 부터는 가지고있는 구조체에서 데이터를 비교해간다.

class Partial:
	def __init__(self, length=0):
		length = length
		after_node = None
	
def Solution(root):
    after = chk_palinderome(root,1)
    return (after.after_node is None and after.length > 1 ) or after.length ==1

def chk_palinderome(root, i):
	if root is None : 
		return Partial(i)
	after = chk_palinderome(root.next, i+1)
	
	if i > (after.length /2):
		 after.after_node = root
	elif i < (after.length /2):
		if root.data == after.after_node.data :
			after.after_node = after.after_node.next
			
	return after