[알고리즘/Python] 연결리스트,리스트 변환

신민정·2020년 11월 17일
1

알고리즘

목록 보기
1/4
post-thumbnail

연결리스트는 시작 또는 끝 지점에 아이템을 추가하거나 삭제,추출하는 작업에는 O(1)에 가능하다. 삽입, 삭제를 할 때는 연결리스트를 이용하는 것이 적절하고 탐색을 할 때는 리스트를 사용하는 것이 적절하다.
또한 리스트는 연산을 쉽게 할 수 있기 때문에, 시간복잡도 문제가 없다면 연결리스트 형태로 입력을 준 경우에는 리스트로 변환해서 쉽게 작업을 수행할 수 있다.

연결리스트를 리스트로 (node2list) 변환하고, 리스트를 연결리스트로 (ㅣlist2node) 변환하는 코드를 작성해보았다.

class Solution:
    def node2list(self, node1: ListNode) -> List: #linked list -> list
        list1 = []
        while node1 != None :
            list1.append(node1.val)
            node1 = node1.next
        return list1
    
    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
        
        
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    	#예제 : 2 두 수의 덧셈 (2 Add Two Numbers) [leetcode](https://leetcode.com/problems/add-two-numbers/)
        node1 = l1
        node2 = l2 
        
        #linked list -> list
        list1 = self.node2list(node1)
        list2 = self.node2list(node2)
        

        # 배열 뒤집기
        list1.reverse()
        list2.reverse()
        
        #배열 -> join -> int
        num1 = int(''.join(str(a) for a in list1))
        num2 = int(''.join(str(a) for a in list2))
        result = list(str(num1+num2))
        result.reverse()
        
        return self.list2node(result) #list -> linked list
profile
안녕나는민정

0개의 댓글