Merge Two Sorted Lists

문제

 

You are given the heads of two sorted linked lists list1 and list2. 

Merge the two lists in a one sorted list. 

The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

 

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4] 
Output: [1,1,2,3,4,4]

 

Example 2:

Input: list1 = [], list2 = [] 

Output: [] 

 

Example 3: 

Input: list1 = [], list2 = [0] 

Output: [0]

 

풀이

# 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]:

    # for문을 두개 돌리지 않는 방법을 생각하자
    # 반복 작업에 필요한 인덱스를 하나 지정해주자 : cur
    # 인덱스는 계속 이동을 해야하니, 인덱스와 같은 주소를 보고있는 결과 노드를 하나더 만들자

 

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

    # 반복 작업에 필요한 인덱스를 하나 지정해주자 : cur
    # 인덱스는 계속 이동을 해야하니, 인덱스와 같은 주소를 보고있는 결과 노드를 하나더 만들자
    dummy = ListNode()
    cur = dummy # dummy와 cur이 같은 주소를 바라보도록 세팅

    # for문을 두개 돌리지 않는 방법을 생각하자
    for i in list1:
    => 이렇게하면 list2에 대한 반복도 필요하다... 좀더 생각해보자

 

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

    dummy = ListNode()
    cur = dummy

    # for문을 두개 돌리지 않는 방법을 생각하자
    while list1 and list2:

       if list1.val <= list2.val:

       else:

        

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

    dummy = ListNode()
    cur = dummy

    while list1 and list2:

       if list1.val <= list2.val:

           # 하나씩 떼어서 붙인다는 생각보다는, 포인터를 주렁주렁 달아버리면 편하다

                cur.next = list1

                list1 = list1.next

       else:

                cur.next = list2

                list2 = list2.next

        cur = cur.next  # cur은 딱히 이전 내용은 기억하지 않고 다음으로 이동(인덱스 역할)

 

    # list1, list2가 남아있는 경우

    if list1:

        cur.next = list1

    elif list2:

        cur.next = list2

   

    return dummy.next