merge.cpp

//
//  main.cpp
//  merge
//
//  Created by 元飞 朱 on 16/6/15.
//  Copyright © 2016年 yuanfei. All rights reserved.
//

#include <iostream>
#include <cassert>

class Node
{
public:
    int data;
    Node* next;
    
    Node(int val, Node* next = nullptr) : data(val), next(next) {};
};

/**
 * Merge two already sorted linked lists
 * Note that this function will mutate the original list.
 *
 * @params: head1, head2 are both sorted linked list
 * @return: the head pointer of the merged linked list
 */
Node* Merge(Node* head1, Node* head2)
{
    Node* p1 = head1;
    Node* p2 = head2;
    
    // a dummy head
    Node* sorted_head = new Node(0);
    Node* sorted_p = sorted_head;
    
    
    while (p1 || p2)
    {
        int v1 = (p1 != nullptr) ? p1->data : INT_MAX;
        int v2 = (p2 != nullptr) ? p2->data : INT_MAX;
        
        if (v1 <= v2) {
            sorted_p->next = p1;
            if (p1 != nullptr)
                p1 = p1->next;
        }
        else {
            sorted_p->next = p2;
            if (p2 != nullptr)
                p2 = p2->next;
        }
        
        // sorted_p is garanteed to not be nullptr
        assert(sorted_p != nullptr);
        
        sorted_p = sorted_p->next;
    }
    
    return sorted_head->next;
}

/**
 * Print a linked list
 *
 * @params: the head pointer of the list
 */
void Print(Node* node)
{
    while (node)
    {
        std::cout << node->data << std::endl;
        node = node->next;
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    Node *h1 = new Node(1, new Node(3));
    Node *h2 = new Node(2, new Node(4));
    
    // normal senario
    Print(Merge(h1, h2));
    
    Node *h3 = new Node(2, new Node(4));
    // one link is empty
    Print(Merge(h3, nullptr));
    
    // both of the lists are empty
    Print(Merge(nullptr, nullptr));
    return 0;
}