21. Merge Two Sorted Lists

• Difficulty: Easy

• Topics: Linked List

• Similar Questions:

  • Merge k Sorted Lists

  • Merge Sorted Array

  • Sort List

  • Shortest Word Distance II

Problem:

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solutions:

/**
 * 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) {
        ListNode* head = NULL;
        ListNode** cur = &head;

        while (l1 != NULL || l2 != NULL) {
            if (l1 == NULL) {
                *cur = l2;
                l2 = l2 -> next;
            }

            else if (l2 == NULL) {
                *cur = l1;
                l1 = l1 ->next;
            }

            else { 
               if (l1->val < l2->val) {
                    *cur = l1;
                    l1 = l1->next;
                } else {
                    *cur = l2;
                    l2 = l2->next;
                }
            }

            cur = &((*cur)->next);
        }

        return head;

    }
};