[LeetCode Road] Merge Two Sorted Lists - Solution/C++

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:

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

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

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.

Source code

Version 1

Idea:
I haven't written a program with ListNode before. So, ListNode's constructor is very strange to me. I directly refered to Huahua's Tech Road.

The method used a temporary node as the start of the result list, named dummy. The ListNode pointer's tail always points to the last node in the result list, so you can use tail->next=l1 to append new Nodes easily.
Notice: Must to do tail=tail->next to get next node' memory address.
The while() proceeds, it means two of ListNode aren't empty. It one of ListNodes is empty, non-empty ListNode is added value to tail. When the processing is done, the result is in dummy.next (because the first value is 0, initial value).

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while(l1 && l2){
            if(l1->val > l2->val){
                tail->next=l2;
                l2 = l2->next;
            }else{
                tail->next=l1;
                l1 = l1->next;
            }
            tail = tail->next;
        }
        if(l1) tail->next = l1;
        if(l2) tail->next = l2;
        return dummy.next;
    }
};