[OJ.leetcode] merge-two-sorted-lists

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

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/* 단순히 two runner를 이용해서 merge sort의 merge와 마찬가지로 O(n)에 sorted list를 merge 하는 알고리즘 한번에 accepted 했어야했는데.. linked list pointing 헷갈려서 2번 실패. 아직 pointer 부분 부족한듯 */ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if(l1 == NULL && l2 == NULL) { return NULL; } else if(l1 == NULL) { return l2; } else if(l2 == NULL) { return l1; } ListNode * head = new ListNode(0); ListNode * cur = head; while(l1 != NULL && l2 != NULL) { if(l1->val > l2->val) { cur->next = l2; l2 = l2->next; } else { cur->next = l1; l1 = l1->next; } cur = cur->next; } if(l1 == NULL) { cur->next = l2; } else if(l2 == NULL) { cur->next = l1; } return head->next; } };