算法（20）-merge不去重-链表-C++

merge单链表。

例如：head1:0->2->3->7
           list2:1->3->5->7->9
结果：0->1->2->3->3->5->7->7->9
 

class Node
{
public:
    int m_value;
    Node* next;
    Node(int value);

};
Node::Node(int value)
{
    m_value = value;
}


Node* mergetwoLists(Node* head1, Node* head2)
{
    if(head1==NULL||head2==NULL)
    {
        return head1 != NULL ? head1 : head2;//如果head1不为空，则返回head1,否则返回head2
    }
    Node* head=head1->m_value< head2->m_value?head1:head2;//head1 head2 谁小取谁
    //cur1是head 值  小的值
    Node* cur1= (head==head1?head1:head2);
    Node* cur2= (head == head1 ? head2: head1);
    Node* pre=NULL;//两个较小的那个
    Node* next = NULL;
    while (cur1 != NULL && cur2 != NULL)
    {
        if (cur1->m_value <= cur2->m_value)//链表1值小
        {
            pre = cur1;
            cur1 = cur1->next;
        }
        else//链表2值小
        {
            next = cur2->next;//保存一下2的下一个点
            pre->next = cur2; //2到1中
            cur2->next = cur1;
            pre = cur2;       //当前指针后移
            cur2 = next;     //2指针后移
        }
    }
      pre->next = cur1 == NULL ? cur2 : cur1;//最后一个节点是cur2或者1
        return head;
}
void printLinkedList(Node* head)
{
    while (head != nullptr)
    {
        cout << "head.value= " << head->m_value << endl;
        head = head->next;
    }

}
 void main()
{

    Node* pnode11 = new Node(0);
    Node* pnode12 = new Node(2);
    Node* pnode13 = new Node(3);
    Node* pnode14 = new Node(7);
    pnode11->next = pnode12;
    pnode11->next->next = pnode13;
    pnode11->next->next->next = pnode14;

    Node* pnode21 = new Node(1);
    Node* pnode22 = new Node(3);
    Node* pnode23 = new Node(5);
    Node* pnode24 = new Node(7);
    Node* pnode25 = new Node(9);
    pnode21->next = pnode22;
    pnode21->next->next = pnode23;
    pnode21->next->next->next = pnode24;
    pnode21->next->next->next->next = pnode25;
    cout << "pnode1 *************" << endl;
    printLinkedList(pnode11);
    cout << "pnode1 *************" << endl;
    printLinkedList(pnode21);

    Node* rcptwo = mergetwoLists(pnode11, pnode21);
    cout << "merge *************" << endl;
    printLinkedList(rcptwo);

}