Approach

• 비교할 list1 또는 list2가 비어있으면 list2, list1을 그대로 반환한다.
• list3을 하나 만들어 시작점을 만들어준다. list1의 val이 더 작다면 list3의 시작점을 list1으로, list2가 더 작다면 list2를 시작점으로 한다.
• 시작점이 된 list는 next로 다음의 노드로 바꿔준다.
• 시작점이 만들어졌으면 이들을 연결시켜줄 길을 만들어줘야한다. path 리스트를 하나 만들고 시작점을 list3으로 설정시켜주었다.
• while문을 통해 하나의 리스트가 NULL이 될때까지 list1, list2의 val값들을 비교하여 path->next 값으로 list를 지정해주고, 지정된 list는 next로 바꿔준다.
• path역시 다음 길로 넘어간다.
• path로 연결된 길들은 list3에서 그대로 적용된다. (처음 path의 node가 list3의 node이기 때문에 path는 길을 연결시켜주는 역할을 하는 listnode이다.)
• list1,2 중 하나가 NULL이 되어 while문을 빠져나오면 NULL이 아닌 list를 path->next에 연결시켜준다.

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == NULL) return list2; // list1의 값이 없으면 list2 반환
        else if(list2 == NULL) return list1;  // list2가 NULL이면 list1 반환.

        ListNode* list3;    // 정답 리스트노드
        if(list1->val < list2->val) // 만약 list1의 첫 밸류가 lsit2 보다 작다면
        {           
            list3 = list1;  //list3의 시작을 list1으로 한다.
            list1 = list1->next;    //list1은 다음의 listnode를 가리킨다.
        }
        else    // list2가 작거나 같으면
        {
            list3 = list2;  //list3의 시작을 list1으로 한다.
            list2 = list2->next;    //list2는 다음의 listnode를 가리킨다.
        }

        ListNode* path = list3; // path는 list3의 처음노드부터 끝까지 길을 이어줄 역할을 하는 노드.

        while(list1 != NULL && list2 != NULL)   // 길을 찾을 listnode 둘 다 NULL이 아니면 비교하는 while문
        {
            if(list1->val < list2->val) // list1의 val이 list2의 val보다 작으면
            {
                path->next = list1; // 다음 길은 list1으로 놓는다.
                list1 = list1->next;    // list1은 list1의 next로 설정
            }
            else    // list2의 val이 list1의 val보다 작거나 같으면
            {
                path->next = list2; // 다음 길은 list2로 설정
                list2 = list2->next;    // list2는 list2의 next로 설정
            }
            path = path->next;  // 다음길을 탐색하기위해 현재node에서 다음node로 바꾼다.
        }

        if(list1 != NULL)   // list1이 NULL이 아니면 list2는 NULL이다. 나머지 노드들을 연결해줌.
        {
            path->next = list1;
        }
        else    // list2 위와 동일.
        {
            path->next = list2;
        }

        return list3;
    }
};

Result

---

추가적인 해결방법

• 재귀를 통해 해결하는 방법이다.
• NULL이 아니면 다음 노드를 mefgeTwoLists함수를 통해 연결시켜준다.
• mergeTwoLists에 매개변수로 값이 작은 list의 다음 노드와 비교하는 list를 넣어준다.

  class Solution {
  public:
      ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
          if(list1 == NULL) return list2; // list1의 값이 없으면 list2 반환
          else if(list2 == NULL) return list1;  // list2가 NULL이면 list1 반환.
  
          if(list1 -> val < list2 -> val)
          {
              list1->next =  mergeTwoLists(list1->next, list2);
              return list1;
          }
          else
          {
              list2->next = mergeTwoLists(list1, list2->next);
              return list2;
          }
      }
  };