Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 연결 리스트(Linked List)가 회문인지 확인하는 프로그램

문제 정의

연결 리스트가 하나 주어져 있을 때, 리스트를 구성하는 요소들이 회문(palindrome)을 이루는지 확인해야 합니다. 회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 순서가 동일한 수열이나 문자열을 의미합니다.

예를 들어 리스트가 [5, 4, 3, 4, 5]라면 어느 방향에서 읽어도 같으므로 회문입니다. 반면 [5, 4, 3, 2, 1]은 뒤집으면 [1, 2, 3, 4, 5]가 되어 원래 순서와 다르므로 회문이 아닙니다.

해결 전략

이 문제는 리스트를 배열에 복사하지 않고도 투 포인터(Two Pointer) 기법과 연결 리스트 뒤집기를 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • slow 포인터는 한 번에 한 칸씩, fast 포인터는 두 칸씩 이동시켜 리스트의 중간 지점을 찾습니다.
  • slow 포인터가 지나가는 노드들을 순회하면서 리스트의 앞부분을 역방향으로 뒤집어 새로운 리스트(rev)를 만듭니다.
  • 중간 지점을 기준으로 왼쪽 절반(뒤집힌 부분)과 오른쪽 절반의 값을 차례대로 비교합니다.
  • 리스트 길이가 홀수라면 가운데 노드는 비교 대상에서 제외하도록 flag 변수로 처리합니다.

알고리즘 단계

  1. fast := head, slow := head, rev := None, flag := 1로 초기화합니다.
  2. head가 비어 있다면 True를 반환합니다.
  3. fast와 fast.next가 모두 존재하는 동안 반복합니다.
    • 만약 fast.next.next가 존재하지 않으면(짝수 길이인 경우) flag := 0으로 설정한 뒤 반복을 중단합니다.
    • fast := fast.next.next (두 칸 전진)
    • temp := slow, slow := slow.next, temp.next := rev, rev := temp (앞부분 뒤집기)
  4. fast := slow.next로 설정하고, slow.next := rev로 연결을 재구성합니다.
  5. flag가 1이면(홀수 길이이면) slow := slow.next로 한 칸 더 이동해 가운데 노드를 건너뜁니다.
  6. fast와 slow가 모두 None이 아닌 동안 두 노드의 값을 비교하고, 하나라도 다르면 False를 반환합니다.
  7. 모든 값이 일치하면 True를 반환합니다.

파이썬 구현 코드

아래 예제를 통해 실제 동작 과정을 더 잘 이해할 수 있습니다.

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

복잡도 분석 및 마무리

이 알고리즘은 fast 포인터로 리스트 끝까지 이동하는 동시에 앞부분을 뒤집고, 이후 절반만 한 번 더 비교하므로 시간 복잡도는 O(n)입니다. 또한 포인터 변수 몇 개만 사용하므로 공간 복잡도는 O(1)로, 리스트 전체를 배열에 담아 비교하는 방식(O(n) 공간 필요)보다 메모리 면에서 훨씬 효율적입니다.

다만 이 방식은 순회 과정에서 원본 리스트의 연결 구조가 변경된다는 점에 유의해야 하며, 원본 유지가 필요하다면 비교가 끝난 뒤 리스트를 다시 복원하는 과정을 추가하면 됩니다.