단일 연결 리스트(singly linked list)가 회문(palindrome)인지 확인해야 하는 경우, 요소를 추가하는 메서드, 특정 노드의 이전 노드를 찾는 메서드, 그리고 회문 여부를 검사하는 메서드를 정의하여 해결할 수 있습니다.
아래는 그 구현 예시입니다.
예제 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList_struct:
def __init__(self):
self.head = None
self.last_node = None
def add_elements(self, data):
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
def get_previous_node(self, ref_node):
curr = self.head
while (curr and curr.next != ref_node):
curr = curr.next
return curr
def check_palindrome(my_list):
beg = my_list.head
end = my_list.last_node
while (beg != end and end.next != beg):
if beg.data != end.data:
return False
beg = beg.next
end = my_list.get_previous_node(end)
return True
my_instance = LinkedList_struct()
my_input = input('연결 리스트에 넣을 요소를 입력하세요: ').split()
for data in my_input:
my_instance.add_elements(int(data))
if check_palindrome(my_instance):
print('이 연결 리스트는 회문입니다')
else:
print('이 연결 리스트는 회문이 아닙니다')실행 결과
연결 리스트에 넣을 요소를 입력하세요: 89 90 78 90 89 이 연결 리스트는 회문입니다
코드 설명
노드 하나를 표현하는 'Node' 클래스를 생성합니다. 각 노드는 데이터(data)와 다음 노드를 가리키는 포인터(next)를 가집니다.
필요한 속성을 갖춘 'LinkedList_struct' 클래스를 생성합니다.
'__init__' 초기화 함수는 첫 번째 노드인 'head'와 마지막 노드인 'last_node'를 모두 'None'으로 설정합니다.
'add_elements' 메서드는 전달받은 데이터를 연결 리스트의 맨 뒤에 새 노드로 추가합니다.
'get_previous_node' 메서드는 지정된 참조 노드 바로 앞에 있는 노드를 찾아 반환합니다.
'check_palindrome' 함수는 리스트의 첫 번째 요소와 마지막 요소를 서로 비교하며, 한 쌍이라도 값이 다르면 해당 리스트는 회문이 아니라고 판단하고 False를 반환합니다. 양쪽 끝에서 안쪽으로 이동하며 모든 쌍이 일치하면 True를 반환합니다.
'LinkedList_struct' 클래스의 인스턴스 객체를 생성합니다.
사용자로부터 연결 리스트에 저장할 요소들을 입력받습니다.
입력받은 각 요소를 정수로 변환하여 연결 리스트에 순서대로 추가합니다.
완성된 연결 리스트에 대해 'check_palindrome' 메서드를 호출합니다.
검사 결과에 따라 적절한 메시지를 콘솔에 출력합니다.
참고: 시간 복잡도와 개선 방법
위 방식에서 'get_previous_node'는 매번 리스트를 처음부터 순회하므로 전체 시간 복잡도는 O(n²)입니다. 더 효율적인 대안으로는 리스트 전체 값을 스택이나 배열에 저장한 뒤 역순과 비교하는 방법(O(n) 시간, O(n) 공간), 또는 리스트의 중간까지 탐색한 후 뒤쪽 절반을 뒤집어 직접 비교한 다음 다시 복원하는 방법(O(n) 시간, O(1) 공간)이 있습니다.