리트코드 문제 23, 24

23. Merge K sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

입력: lists = [[1,4,5],[1,3,4],[2,6]]

출력: [1,1,2,3,4,4,5,6]

풀이 1: 브루트 포스 방법을 이용

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        nodes = []
        head = point = ListNode(0)
        # nodes 리스트에 lists 안의 연결리스트 값을 append 한다.
        for l in lists:
            while l:
                nodes.append(l.val)
                l = l.next
                
        # 정렬한 nodes 안의 숫자를 연결리스트의 형태로 만든다.
        for x in sorted(nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next

• 먼저 nodes 리스트에 lists 안의 연결리스트 값을 append 한다.
• sorted를 통해 nodes를 정렬하고 리스트를 연결리스트의 형태로 변경해준다.
• memory usage가 16.18%로 그리 좋은 방법은 아닌 것 같다.

풀이 2: 분할 정복

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not len(lists):
            return None
        
        # 모든 연결리스트를 합칠때까지 실행한다.
        while len(lists) > 1:
            newLists = [] 
            
            # 분할 정복하여 두개의 연결리스트를 합친다.
            for i in range(0, len(lists), 2):
                LL1 = lists[i]
                LL2 = lists[i + 1] if (i + 1) < len(lists) else None
                
                # 연결리스트 LL1과 LL2를 합친다.
                mergedList = self.merge2List(LL1, LL2)
                newLists.append(mergedList)
            lists = newLists
        return lists[0]
    
    # 두 개의 연결리스트를 한개로 합친다.            
    def merge2List(self, l1, l2):
        dummy = ListNode()
        current = dummy
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
            
        # l1 또는 l2 중 한개가 None이면 None이 아닌 연결리스트를 current 뒤에 붙인다.
        if l1:
            current.next = l1
        if l2:
            current.next = l2
            
        return dummy.next

• 분할 정복하여 lists의 요소가 절반으로 줄어들때까지 for 문을 실행한다.
• 모든 연결리스트가 하나로 합쳐질때까지 while 문을 실행한다.
• merge2List는 두개의 연결리스트를 하나로 합치는 함수이다.
• memory usage가 74.22%로 브루트 포스 방법보다 성능이 좋은 것을 알 수 있다.

---

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

입력: head = [1,2,3,4]

출력: [2,1,4,3]

내 풀이

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        start = prev = ListNode(None)
        prev.next = head
        while head and head.next:
            back = head.next
            head.next = back.next
            back.next = head
            prev.next = back
            prev = prev.next.next
            head = head.next
            
        return start.next

• back은 head 다음 노드이다.
• head의 다음 노드를 back의 다음 노드와 연결시킨다.
• back의 다음 노드를 head와 연결시킨다.
• head의 전 노드, prev를 back에 연결 시킨다.
• prev와 head를 각각 다음 노드로 움직인다.

결과

Runtime: 48 ms, faster than 53.60% of Python3 online submissions for Swap Nodes in Pairs. Memory Usage: 13.8 MB, less than 97.50% of Python3 online submissions for Swap Nodes in Pairs.

풀이 1: 재귀구조

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head and head.next:
            p = head.next
            head.next = self.swapPairs(p.next)
            p.next = head
            return p
        
        return head

중요내용

• p는 head의 다음 노드이다.
• p의 다음노드, 즉 head의 다음 다음 노드를 swapPairs에 재귀로 넣어준다.
• 제일 끝에 있는 노드부터 차례대로 스와핑이 된다.