연결리스트 / (문제) 팰린드롬 연결리스트

---

연결리스트 만들기

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

head_node = ListNode(1)
head_node.next = ListNode(2)
head_node.next.next = ListNode(3)
head_node.next.next.next = ListNode(4)

def printNoded(node:ListNode):
    crnt_node = node
    while crnt_node is not None:
        print(crnt_node.val, end=' ')
        crnt_node = crnt_node.next
            
def printNodeRecur(node:ListNode):
    print(node.val, end=' ')
    if node.next is not None:
        printNodeRecur(node.next)

 

연결리스트를 만들 때 처음에는 받아온 val 을 넣고 다음 노드는 가리키는 next는 None으로 설정한다.

head_node.next 코드는 다음 노드를 가리키는 코드이다. 현재 노드의 다음 노드에 ListNode(데이터) 코드를 작성하여 데이터를 넣는다.

	head	Node(1)	Node(2)	Node(3)
val	1	2	3	4
next	Node(1)	Node(2)	Node(4)	x

데이터를 보기 위해서 2가지 방식이 있다. (iterator / recursive)

iterator 방식은 for문, while문 처럼 돌면서 보여준다.

crnt_node (현재노드) 에 받아온 노드를 받는다.

crnt_node 가 비어있지 않다면 현재의 노드의 값을 보여준다. 

crnt_node 는 현재 노드가 가리키고 있는 다음 노드를 가리키게 한다.

---

연결 리스트를 리스트로 변환 (LinkedList -> List) 

def node2list(self, node1: ListNode) -> List: #linked list -> list
        list1 = []
        while node1 != None :
            list1.append(node1.val)
            node1 = node1.next
        return list1

연결 리스트로 받은 데이터가 node1 이다. (연결리스트는 노드로 되어있어 ListNode 로 표현한다.)

 

링크드 리스트의 특징을 조금 이야기 해보자.

3개의 값이 있는 링크드 리스트가 있다. 

입력 값 중 3번째 값에 접근을 하기 위해서는 링크드 리스트의 첫번째 노드인  head 노드에서 부터 시작이 된다.

(링크드 리스트가 파라미터로 던져지는 경우 head라고 표현을 하는 이유 또한 그렇다.)

head 에서 포인터가 가리키는 다음 노드로 이동 후 다시 다음 노드로 이동을 해야한다.

설명을 참고하여 코드를 살펴보면 

 

node1 != None  | -> 헤드에 아무것도 있지가 않다면 연결 리스트는 비어있다는 말이다.

연결리스트의 하나의 노드에는 다음 노드를 가리키는 주소값(next)과 데이터(val)를 저장하고 있다.

node1.val | -> 값을 받아오기 위해서는 해당노드.val 을 사용한다.

list.append(node1.val) | -> 노드의 값을 생성한 리스트에 하나씩 append 하여 연결리스트를 리스트로 변환한다.

node1.next | -> 다음 노드를 가리키기 위해서는 해당 next를 사용해서 나타낸다.

 

 

---

리스트를 연결리스트로 변환 (List to LinkedList)

 def list2node(self, list1: List) -> ListNode:
        result_node = ListNode()
        
        for i,num in enumerate(list1):
            if i == 0 :
                result_node.val = num
            else :
                node = result_node
                while node.next != None:
                    node = node.next
                node.next = ListNode(num)
        return result_node

 

리시트를 연결리스트로 변환하기 위해서는 연결리스트의 특징인 노드를 활용하여 변환하여야한다.

노드를 생성한다.

해당 노드에 리스트에 있는 값을 넣어준다.

 

)_( 다시다시!~~

 

 

---

팰린드롬 연결리스트

연결 리스트가 팰린드롬 구조인지 판별하라

 

연결리스트는 노드에 삽입, 삭제에 있어서 실행시간이 짧은 반면 검색 시 O(n)의 시간이 소비된다.

반면에 리스트는 삽입, 삭제에 O(n)의 시간이 걸리지만 검색에 있어서 따 빠른 실행 시간이 걸리기에 검색, 탐색의 경우 리스트를 사용하는 것이 좋다.

 

그렇다면 문제가 검색을 요하는 경우 연결리스트로 데이터가 들어온 경우 어떻게 해야할까?

해당 문제의 경우에는 연결 리스트를 리스트로 변환시켜 문제를 풀도록 한다.

 

input : 1 -> 2   /  1 -> 2-> 2-> 1
output : False	/	True

def palin_linked(self, head:ListNode)-> bool:
    q = []
    if not head:
        return True
    #연결리스트 to 리스트
    node = head
    while node is not None:
        q.append(node.val)
        node = node.next
	#팰린드롬 check
    while len(q) > 1:
        if(q.pop(0) != q.pop()):
            return False
    return True

q라는 리스트를 생성한다.

head가 존재하지 않으면 아무것도 없기에 팰린드롬은 true이다.

이제 연결리스트를 리스트로 변환한다.

현재의 node는 head를 가리킨다. 노드가 비어있지 않다면 리스트에 노드의 값을 넣는다. 그리고 현재 노드는 다음 노드를 가리킨다. while 문을 통해서 연결리스트 노드의 값들이 리스트로 모두 변환된다.

리스트의 길이가 1보다 크다면 (만약 1보다 작다면 아무것도 없기에 팰린드롬이 된다. => true)

리스트의 앞과 뒤에서 각각 값들을 빼면서 비교를 한다.