[LeetCode] Merge Two Sorted Lists

연결리스트 문제는,, 첨 풀어봐서 ~ 검색해보고 아이디어를 얻어서 힘겹게 ㄱ ㅡ풀어냈다

(이게 easy라니 이게easy라니 이게easy라니 죽자)

 

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

Merge the two lists into 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]

 

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

두 개의 리스트가 주어지는데, 이 오름차순으로 정렬 되어 있는 리스트들을 합친 리스트를 반환하는 문제이다.

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
#define MAX_SIZE    100

// 최대 MAX_SIZE개의 ListNode 객체를 담을 수 있는 배열
struct ListNode nodePool[MAX_SIZE];
int currentIndex = 0;

// 새로운 노드 생성 함수
struct ListNode* createNode(int value){
    // 리스트의 크기가 최대 사이즈보다 클 경우 NULL 반환
    if(currentIndex >= MAX_SIZE) {
        return NULL;
    }

    // nodePool의 현재 인덱스를 새로운 노드로 사용
    struct ListNode* newNode = &nodePool[currentIndex++];
    newNode->val = value;
    newNode->next = NULL;

    return newNode;
}
 
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy;
    struct ListNode* current = &dummy; // 현재 위치를 가리킬 포인터
    dummy.next = NULL;

    // 두 리스트를 순회하며 작은 값을 선택
    while(list1 != NULL & list2 != NULL) {
        if(list1->val <= list2->val){
            current->next = list1; //list1의 현재 노드를 병합 리스트에 추가
            list1 = list1->next;
        } else {
            current->next = list2;
            list2 = list2->next;
        }
        current = current->next;
    }

    // 남아있는 요소들을 병합 리스트에 추가
    if(list1 != NULL){
        current->next = list1;
    }else {
        current->next = list2;
    }
    // 병합된 리스트의 시작점 반환
    return dummy.next;
}

 

/* 문제를 해결하면서 헷갈렸던 것들 정리 ,,, */

 

먼저, struct ListNode는 연결 리스트의 각 노드를 표현하는 구조체로, 

val : 노드의 값

next : 다음 노드를 가리키는 포인터 

 

nodePool은 ListNode 구조체를 최대 100개 담을 수 있는 배열이다. 배열은 각 요소가 ListNode 구조체인 일종의 저장 공간이 되는것!

(== nodePool은 ListNode 구조체로 이루어진 배열이다)

 

dummy : 병합된 리스트의 시작을 추적하는 더미 노드.

current : 병합된 리스트에서 현재 위치를 가리키는 포인터

currentIndex : nodePool 배열에서 새로운 노드를 할당할 때 사용하는 인덱스를 추적하는 변수