[문제풀기] 연결리스트 _ Palindrome Linked List

연결 리스트(Linked List)

노드(node)들이 포인터로 서로 연결되어 있는 자료구조
노드 : 데이터와 다음 노드를 가르키는 포인터(주소)

1. 단일 연결 리스트(Singly Linked List)
각 노드는 데이터 필드와 다음 노드를 가르키는 포인터 필드로 구성된다.
마지막 노드의 포인터 필드 값은 보통 NULL이며, 이는 리스트의 끝을 나타낸다.

장점)
삽입, 삭제가 효율적이고 간단하다. 앞, 뒤 노드만 수정하면 되기 때문에
동적 크기 조정이 가능하다.
단점)
특정 위치에 직접 접근하기 위해서는 처음부터 순차적으로 탐색해야 한다. (탐색시간 증가)

2. 이중 연결 리스트(Doubly Linked List)
각 노드는 데이터 필드와 이전 노드를 가리키는 포인터 필드, 다음 노드를 가리키는 포인터 필드로 구성된다.
첫 번째 요소, 마지막 요소에 대한 접근이 가능하다.

장점)
양방향으로 탐색이 가능하여 특정 위치에서의 삽입과 삭제가 단일 연결리스트보다 효율적이다.
역방향 탐색 및 반대방향에서의 삽입/삭제가 가능하다.
단점)
이전(prev) 포인터를 유지해야하므로 추가 메모리 공간을 사용한다.

---

문제 : Palindrome Linked List

단일 연결 리스트가 주어졌을 때, 이 리스트가 팰린드롬이라면 true를, 아니라면 false를 반환한다.

 

예시1:

입력: lst = [1, 2, 2, 1]

출력: true

 

예시2:

입력: lst = [1, 2]

출력: false

---

나의 풀이

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def isPalindrome(self, head):
        values = [] # 빈 리스트 생성
        current = head

        while current:
            values.append(current.val)
            current = current.next # 현재 노드의 다음 노드로 업데이트            

        return values == values[::-1] # 파이썬에서는 [::-1]을 사용해서 리스트를 뒤집을 수 있음
    
def createLinkedList(lst):
    if not lst:
        return None
    head = ListNode(lst[0])
    current = head
    for i in range(1, len(lst)):
        current.next = ListNode(lst[i])
        current = current.next
    return head
    
solution = Solution()
lst = createLinkedList([1,2,3,3,2,1])
print(solution.isPalindrome(lst))

# 결과 : true