Leetcode # 21. Merge Two Sorted Lists

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

Solution

Time Complexity: O(length(list1) + length(list2))
Space Complexity: O(1)

class Solution {
public:
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode *cur1 = list1, *cur2 = list2, 
             *root = new ListNode(0), 
             *cur  = root;

    while(cur1 != NULL || cur2 != NULL){
      if(cur1 == NULL || cur2 == NULL){
        cur->next = cur1 == NULL ? cur2 : cur1;
        break;
      }

      // cur1 != NULL && cur2 != NULL
      if(cur1->val > cur2->val){
        cur->next = cur2;
        cur2 = cur2->next;
      }else{
        cur->next = cur1;
        cur1 = cur1->next;
      }
      cur = cur->next;
    }

    return root->next;
  }
};

Last Updated on 2023/08/16 by A1go