Merge Two Sorted Lists--LeetCode-蒲公英云

Merge Two Sorted Lists--LeetCode

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.

/*
始终将second链表节点插入到first链表中 
*/
List* Merge_list(List* first,List* second)
{
    List* result = first;
    List* pre;
    if(first->value > second->value)
    {
        pre = first;
        first = second;
        second = pre;
    }
    //始终将second链表中的节点插入到first链表中 
    while(first->next!=NULL && second != NULL)
    {
        if(first->next->value > second->value)
        {
            pre = second->next;
            second->next = first->next;
            first->next = second;
            second = pre;
        }
        else
            first = first->next;
    }    
    if(second != NULL)
    {
        first->next=second;
    } 
    return result;
}

思路：还有一种方法，就是使用一个新的节点将两个链表进行连接。借助一个新的节点。

List* MergeList(List* first,List* second)
{
    List* head = new List;
    List* cur;
    head->next = NULL;
    cur = head;
    while(first != NULL && second !=NULL)
    {
        if(first->value <second->value)
        {
            cur->next = first;
            first = first->next;
        }
        else
        {
            cur->next = second;
            second = second->next;
        }
        cur = cur->next;
    }
    if(first == NULL)
        cur->next = second;
    else
        cur->next = first;
    return head->next;
}