파이썬 알고리즘 - 링크드리스트(LinkedList) 회문(대칭) 출력

개발자 면접 트레이딩 - 파이썬 알고리즘 문제(10)

 

(1). 개발자 면접 트레이닝 - 링크드리스트(LinkedList) 회문(대칭) 출력하기

① 링크드리스트(LinkedList)를 역으로 출력하는 것이 포인트

② 링크드리스트를 정확히 생성하고 역으로 출력하는 것이 중요

③ 링크드리스트의 회문(역)을 리턴

④ 예를들어 [2, 3, 5, 3, 2]  의 회문은 [2, 3, 5, 3, 2] 으로써 결과값은 같다.

 

 

(2). 소스 코드

PYTHON

#palindrome_linkedlist.py
import unittest

class Node:
    def __init__(self, item):
        self.val = item
        self.next = None

class LinkedList:
    def __init__(self, item):
        self.head = Node(item)

    def add(self, item):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(item)

    def getHead(self):
        return self.head

    def reverse(self):
        prev = None
        cur = self.head
        while cur is not None:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        self.head = prev

    def printlist(self):
        cur = self.head
        res = []
        while cur is not None:
            res.append(cur.val)
            cur = cur.next
        return str(res)

def solution(list):
    input = list.printlist()
    list.reverse()
    output = list.printlist()
    if input == output:
        return True
    else:
        return False

class LinkedListTest(unittest.TestCase):
    def test(self):
        list1 = LinkedList(2)
        list1.add(3)
        list1.add(5)
        list1.add(3)
        list1.add(2)

        list2 = LinkedList(3)
        list2.add(6)
        list2.add(8)

        self.assertEqual(True, solution(list1))
        self.assertEqual(False, solution(list2))

unittest.main()

 

(3). 소스 코드 분석

① 14 라인 : 헤드(Head) 노드 선언

② 24 라인 : 현재 링크드리스트(LinkedList)의 헤드 반환 함수 선언

③ 28 라인 : 링크드리스트를 회문(역)으로 만드는 메소드 선언

④ 39 라인 : 회문(역)으로 만들어진 링크드리스트를 문자열로 변환

⑤ 49 라인 : 두 링크드리스트를 비교하는 메소드 선언

⑥ 59 ~ 끝 : 링크드리스트(LinkedList) 선언 및 assertEqula 단위 테스트 함수를 사용하여 입력 결과와 출력결과를 비교

 

LinkedList(링크드리스트) 관련 알고리즘 문제는 자주 활용, 출제 되므로 Java, C  등으로 작성해보자.

 

(4). 실행결과1 - 단위테스트 정상 출력(회문 비교 결과 같을 경우)

 

 

(5). 실행결과2 - 단위테스트 에러 출력(회문 비교 다를 경우)