Thursday, November 30, 2017

Merge two sorted linked lists and return it as a new 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.

 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void MoveNode (ListNode** destNode, ListNode** srcNode) {
        ListNode* newNode = *srcNode;
        if (!newNode)
            return;
        *srcNode = newNode->next;
        newNode->next = *destNode;
        (*destNode) = newNode;
       
           
    }
       
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* t1 = l1;
        ListNode* t2 = l2;
        ListNode* result = new ListNode(0);
        ListNode* t3 = result;
       
        if (!t1 && !t2) return t1;
        if (!t1 && t2) return t2;
        if (t1 && !t2) return t1;
       
        while (t1 && t2) {
            if (t1->val <= t2->val) {
                MoveNode(&(t3->next), &t1);
            } else {
                MoveNode(&(t3->next), &t2);
            }
            t3 = t3->next;
        }
       
        while (t1) {
            MoveNode(&(t3->next), &t1);
            t3 = t3->next;
        }
       
        while (t2) {
            MoveNode(&(t3->next), &t2);
            t3 = t3->next;
        }

    return result->next;
    }
};

No comments:

Post a Comment