LeetCode. Merge Two Sorted Lists [Linked List]

Problem:

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

 

Example:

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

 

-Summary-

1. Create a dummy and curr variables to track and merge the two lists.

2. Compare l1 and l2 value. 'curr' will connect to the less value. Update l1 or l2 depends on the result

3. Move the curr position

4. After the loop, connect curr to any left l1 or l2 LinkedList

 

처음엔 어떻게 해야할지 감이 안오다가, Leetcode 의 discussion에서 많은 도움을 받았다.

또한 이번 문제를 풀면서, 아래와 같은 코드 기법도 알게 되었다.

 

curr.next = l1 or l2
#cur.next = l1 if l1 else l2

 

-다른 방식으로 푼 Code-

재귀함수를 이용한 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if (not l1) or (l2 and (l1.val > l2.val)):
            l1, l2 = l2, l1
        
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        
        return l1

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]