[LeetCode] Merge Two Sorted List

Problem : Merge Two Sorted List

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.

Analysis:
Not a difficult problem. But make clear whether we need a new (created) list, or just the merged one.
A dummy node at first will be very helpful and no need to worry about how to get the pointer to the first node.



Code

#include <iostream>

//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 dummy = ListNode(0);
        ListNode* cursor = &dummy;
        ListNode* tmp=NULL;
        while(l1||l2)
        {
            if(l1==NULL) {cursor->next=l2; break;}
            if(l2==NULL) {cursor->next=l1; break;}
            if(l1->val<l2->val)
            {
                tmp=l1->next;
                l1->next=NULL;
                cursor->next=l1;
                cursor=cursor->next;
                l1=tmp;
            }
            else
            {
                tmp=l2->next;
                l2->next=NULL;
                cursor->next=l2;
                cursor=cursor->next;
                l2=tmp;
            }
        }
        return dummy.next;
    }
};

int main()
{
    Solution s;
    {
        ListNode* result = s.mergeTwoLists(NULL, NULL);
        std::cout << "\n";
    }

    {
        ListNode n1(1), n2(2);
        n1.next = &n2;
        ListNode* result = s.mergeTwoLists(&n1,NULL);
        std::cout << "\n";
    }

    {
        ListNode n1(1), n2(2);
        n1.next = &n2;
        ListNode* result = s.mergeTwoLists(NULL, &n1);
        std::cout << "\n";
    }

    {
        ListNode n1(1), n2(2), n3(3), n4(4);
        n1.next = &n4;
        n2.next = &n3;
        ListNode* result = s.mergeTwoLists(&n1,&n2);
        std::cout << "\n";
    }


    return 0;
}