Merge Two Sorted Lists--LeetCode

àì夳堔傛蜴生んèń 2022-08-07 13:40 10阅读 0赞

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;
    }