数据结构-->单链表OJ题--->讲解_04

本期我们讲解一道 ：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表所有结点组成的。

现附上图示样例 ：

现在上手代码 :>

SLTNode* CombineLists(SLTNode* list1,  ,SLTNode* list2)
{
	if(list1 == NULL)
    	return list2;
    if(list2 == NULL)
        return list1;
    SLTNode* cur1 = list1, cur2 = list2;
    SLTNode* head = NULL, *tail = NULL;
    
    while(cur1 && cur2)
    {
    		if(cur1 ->data < cur2 ->data)
            {
            	if(head == NULL)
                {
                	head = tail = cur1 ->data;
                }
                else
                {
                	tail ->next = cu1 ->data;
                    tail = tail ->next;
                }
                cur1 = cu1 ->next;
            }
        	
        	else
            {
            	if(head == NULL)
                {
                	head = tail = cur2 ->data;
                }
                else
                {
                	tail ->next = cur2 ->data;
                    tail = tail ->next;
                }
                cur2 = cur2 ->next;
            }
    }
    
    // 将剩余链表（过长的那个链表）直接链接在尾部
    if(cu1)
    {
    	tail ->next = cur1;
    }
    
    if(cur2)
    {
    	tail ->next = cur2;
    }
   
    return head;	
}

以上情况也适用于 :>

1.两个链表的长短不一！！

2.以及空链表的特殊情况！！

3.有一个为空，有一个有数据结点！！ 

现在，对代码优化处理，设置哨兵位进行简化逻辑！！

代码如下 :>

SLTNode* CombineLists(SLTNode* list1,  ,SLTNode* list2)
{
    SLTNode* cur1 = list1, cur2 = list2;
    SLTNode* guard = NULL, *tail = NULL;
    
    STNode* guard = (STNode*) malloc(sizeof(STNode);
    STNode* tail = (STNode*) malloc(sizeof(STNode);
    tail ->next = NULL;		//防止尾指针乱窜
                                    
    while(cur1 && cur2)
    {
    		if(cur1 ->data < cur2 ->data)
            {                           
                	tail ->next = cu1 ->data;
                   	tail = tail ->next;                
                	cur1 = cu1 ->next;
            }
        	
        	else
            {
                	tail ->next = cur2 ->data;
                    tail = tail ->next;
                	cur2 = cur2 ->next;
            }
    }
                                    
    // 将剩余链表（过长的那个链表）直接链接在尾部    
    if(cu1)
    {
    	tail ->next = cur1;
    }
    
    if(cur2)
    {
    	tail ->next = cur2;
    }
   
	free(guard);
	STNode* head = guard ->next;                                                                       
    return head;	
}

其实，优化后的链表最大的优点是 :> 不再需要对头部结点进行判空处理！！

至此，双链表合并完成！！