[leetcode]21 두 연결리스트의 병합

https://leetcode.com/problems/merge-two-sorted-lists/submissions/

LeetCode - The World's Leading Online Programming Learning Platform

문제 : 정렬되어 있는 두 연결 리스트를 합쳐라

 

입력 : 1->2->4, 1->3->4

 

출력 : 1 ->1->2->3->4->4

 

문제 해결 방법

 

1. 두 연결 리스트를 리스트로 변환 후 다시 연결리스트로 변환

 

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        result =[]
        
        node = list1


#첫번째 연결 리스트 리스트로 변환
        while node is not None:
            result.append(node.val)
            node =node.next
        
        node2 = list2
        

#두번째 연결 리스트 리스트로 변환
        while node2 is not None:
            result.append(node2.val)
            node2= node2.next
        
        #리스트 정렬
        result.sort()
       
       #리스트에 들은 것이 있다면 
        if len(result)>0:
            head = ListNode()
            head.val = result[0]
            current =head

            for i in range(1,len(result)):
                node = ListNode()
                node.val = result[i]
                current.next =node
                current = current.next


        else : 
            return None

        return head

 

내가 처음에 오류가 났던 이유

 

1. 리스트에 들은 것이 없을 수도 있는데 할당해주려고 함 -> 할당할 수 없기 때문에 오류

#리스트에 들은 것이 있다면 
        if len(result)>0:
            head = ListNode()
            head.val = result[0]
            current =head

            for i in range(1,len(result)):
                node = ListNode()
                node.val = result[i]
                current.next =node
                current = current.next

 

사용된 개념

 

1. 리스트 -> 연결리스트

2. 연결리스트 -> 리스트

 

 

 

2. 재귀를 통한 병합

 

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        if (not list) or (list2 and list1.val>list2.val):
            list1 ,list2 = list2 ,list1
        
        if list1:
            list1.next = self.mergetTwoLists(list1.next,list2)
        
        return list1