LinkedList : merge two sorted lists

 

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

Merge Two Sorted Lists - LeetCode

 

list1 과 list2는 이미 정렬되어 있다.

그러니까 각 리스트의 맨 앞 노드 (제일 작은값)만 비교해서 더 작은값을 이용해 새 리스트를 만들어주면 된다.

두 리스트를 이용해 결과 리스트를 만들라고 하는것으로 보아 공간복잡도를 O(1)으로 하라는 것 같다.

 

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        result = ListNode() # 결과 리스트를 만들기 위한 더미노드
        p = result # 결과 리스트에 노드를 추가해주기 위한 포인터
        lp = list1 # 첫 번째 리스트의 포인터 
        rp = list2 # 두 번째 리스트의 포인터

        while lp and rp:
            if lp.val < rp.val:
                p.next = lp # 결과 리스트 포인터가 더 작은값을 가진 노드를 가리키게 하고
                p = lp # 결과 리스트에 새로 추가된 노드로 포인터를 옮긴다.
                lp = lp.next # 그리고 list1을 가리키는 포인터는 그 다음값으로 옮긴다.
            else:
                p.next = rp
                p = rp
                rp = rp.next
        if lp:
            p.next = lp

        if rp:
            p.next = rp

        return result.next