[LeetCode] 21. Merge Two Sorted Lists

Question :
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 1 :

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2 :

Input: l1 = [], l2 = []
Output: []

Example 3 :

Input: l1 = [], l2 = [0]
Output: [0]

Constraints :

The number of nodes in both lists is in the range [0, 50]

-100 <= Node.val <= 100

Both l1 and l2 are sorted in non-decreasing order.

Node :

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) {}
}

Solution.h

#include<iostream>
#include<malloc.h>
typedef 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* l1, ListNode* l2);

    
};

Solution.cpp

#include "Solution.h"

ListNode* Solution::mergeTwoLists(ListNode* l1, ListNode* l2)
{
	ListNode* sort_list = new ListNode(0);
	ListNode* header = sort_list;
	if (l1 == NULL && l2 == NULL) {
		return nullptr;
	}

	else if (l1 == NULL && l2 != NULL) {
		return l2;
	}
	else if (l1 != NULL && l2 == NULL) {
		return l1;
	}

	while (l1 != NULL && l2 != NULL) {
		if (l1->val <= l2->val) {
			header->val = l1->val;
			l1 = l1->next;
			header->next = (ListNode*)malloc(sizeof(ListNode));
			if(l1!=NULL){
			header->next = new ListNode(0);
			header = header->next;
			}
		
		}
		else {
			header->val = l2->val;
			l2 = l2->next;
			header->next = (ListNode*)malloc(sizeof(ListNode));
			if (l2 != NULL) {
				header->next = new ListNode(0);
				header = header->next;
			}
			
		}
	}

	if (l1 == NULL) {
		header->next = l2;
	}
	else if (l2 == NULL) {
		header->next = l1;
	}
	return sort_list;
}

Main.cpp

* malloc 사용 동적 할당, memset 초기화 ,struct 생성 초기화 다양한 사용 추구.

#include"Solution.h"
#include<vector>


int main(int argc, char* argv[]) {
	ListNode* node_1;
	ListNode* node_2;
	node_1 = (ListNode*)malloc(sizeof(ListNode));
	memset(node_1, 0, sizeof(ListNode));
	node_2 = (ListNode*)malloc(sizeof(ListNode));
	memset(node_2, 0, sizeof(ListNode));
	ListNode* temp_node_1 = (ListNode*)malloc(sizeof(ListNode));
	node_1->next = temp_node_1;
	ListNode* temp_node_2 = (ListNode*)malloc(sizeof(ListNode));
	node_2->next = temp_node_2;
	std::vector<int> arr_1 = { 1, 2, 3 };
	std::vector<int> arr_2 = { 1, 3, 5 };
	for (int loop_i=0; loop_i < arr_1.size(); loop_i++) {
		if (loop_i == arr_1.size() - 1) {
			temp_node_1->val = arr_1[loop_i];
			temp_node_1->next = NULL;
			break;
		}
		temp_node_1->val = arr_1[loop_i];
		temp_node_1->next = (ListNode*)malloc(sizeof(ListNode));
		temp_node_1 = temp_node_1->next;

	}

	for (int loop_j = 0; loop_j < arr_2.size(); loop_j++) {
		if (loop_j == arr_2.size() - 1) {
			temp_node_2->val = arr_2[loop_j];
			temp_node_2->next = NULL;
			break;
		}
		temp_node_2->val = arr_2[loop_j];
		temp_node_2->next = (ListNode*)malloc(sizeof(ListNode));
		temp_node_2 = temp_node_2->next;

	}

	
	Solution* sol = new Solution();
	sol->mergeTwoLists(node_1->next, node_2->next);
	return 0;

}

Result :
Runtime: 8 ms, faster than 84.76% of C++ online submissions for Merge Two Sorted Lists.
Memory Usage: 15.7 MB, less than 7.11% of C++ online submissions for Merge Two Sorted Lists.

 

GitHub : github.com/Anchangun

Anchangun - Overview