[leetcode] merge-two-sorted-lists.py

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

Merge Two Sorted Lists - LeetCode

 

두개의 연결리스트를 하나로 합치는 문제 입니다.

이미 정렬이 되어있는 리스트 이기 때문에 두 연결리스트의 노드를 순회 하면서 둘중 더 작은 노드를  node.next 로 지정해서 나아가면 됩니다. get_next는 다음 노드를 정하는 함수 입니다. go_next는 노드 여부에 따라 진행할지 말지 정하는 함수입니다.

 

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

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        
        def get_next(l1, l2):
            if l1 == None and l2 == None:
                return (None, None, None)
            if l1 == None:
                return (l2, l1, l2.next)
            elif l2 == None:
                return (l1, l1.next, l2)
            elif l1.val < l2.val:
                return (l1, l1.next, l2)
            else:
                return (l2, l1, l2.next)
        
        def go_next(node, l1, l2):
            next_node, l1, l2 = get_next(l1, l2)
            if l1 is None and l2 is None:
                if node is not None:
                    node.next = next_node
                return node
            node.next = go_next(next_node, l1, l2)
            return node
        next_node, l1, l2 = get_next(list1, list2)
        return go_next(next_node,l1, l2)

 

Discuss에 있는 간단한 코드:

개념은 비슷하지만.. 훨씬, 아주 간단하게 만들었다.

class Solution:
    def mergeTwoLists(self, a, b):
        if a and b:
            if a.val > b.val:
                a, b = b, a
            a.next = self.mergeTwoLists(a.next, b)
        return a or b

출처