문제 개요
연결 리스트(Linked List)가 하나 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 이 리스트의 요소들이 회문(palindrome)을 이루는지 확인하는 것입니다. 예를 들어 리스트가 [1, 2, 3, 2, 1]이라면 앞에서부터 읽으나 뒤에서부터 읽으나 순서가 같으므로 회문입니다.
이 문제는 추가 배열 없이 투 포인터(Fast & Slow Pointer) 기법과 연결 리스트 앞부분 반전을 조합하면 시간 복잡도 O(n), 공간 복잡도 O(1)만으로 해결할 수 있습니다.
해결 단계
- fast := head, slow := head, rev := None, flag := 1로 초기화합니다.
- head가 비어 있다면 즉시 True를 반환합니다.
- fast와 fast.next가 존재하는 동안 아래를 반복합니다.
- fast.next.next가 존재하지 않으면(리스트 길이가 홀수라는 의미) flag := 0으로 설정하고 반복을 종료합니다.
- fast를 두 칸 전진시킵니다.
- slow를 한 칸 전진시키면서, 지나온 노드를 rev에 역방향으로 연결하여 앞쪽 절반을 뒤집습니다.
- fast := slow.next로 설정하고, slow.next := rev로 연결을 뒤집습니다.
- flag가 설정되어 있으면(노드 수가 홀수인 경우) 가운데 노드를 건너뛰기 위해 slow를 한 칸 더 전진시킵니다.
- fast와 slow가 모두 None이 아닌 동안 두 노드의 값을 비교하고, 값이 다르면 False를 반환합니다.
- 모든 비교가 일치하면 True를 반환합니다.
Python 구현 예제
아래 구현을 통해 더 자세히 이해해 보겠습니다.
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([1,2,3,2,1])
ob1 = Solution()
print(ob1.isPalindrome(head))입력
[1,2,3,2,1]
출력
True
마무리
이 알고리즘은 느린 포인터(slow)가 리스트 중간에 도달할 때까지 빠른 포인터(fast)를 이용해 앞쪽 절반을 제자리에서 뒤집습니다. 이후 뒤집힌 앞쪽 절반과 남은 뒤쪽 절반을 한 노드씩 비교하여 회문 여부를 판단합니다. 홀수 길이의 리스트는 가운데 노드를 비교 대상에서 제외하기 위해 flag 변수를 사용한다는 점이 핵심입니다.