[数据结构与算法][ 链表OJ题 5 ] 合并两个有序链表

目录

题目来源：

代码实现：

?分析过程：

题目来源：

21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

代码实现：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1==NULL) return list2;
    if(list2==NULL) return list1;
    struct ListNode* head = NULL,*tail = NULL;
    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {
            if(tail == NULL)
            {
                head = tail = list1;
            }
            else
            {
                tail->next = list1;
                tail = list1;
            }
            list1 = list1->next;
        }
        else
        {
            if(tail == NULL)
            {
                head = tail = list2;
            }
            else
            
            {
                tail->next = list2;
                tail = list2;
            }
            list2 = list2->next;
        }

    }
    if(list1)
    {
        tail->next = list1;
    }
     if(list2)
    {
        tail->next = list2;
    }
    return head;
}

?分析过程：

?在本题中，我们需要创建2个新的结构体指针head和tail，分别用来表示合成后链表的头和尾，因此在合成前，我们要将head和tail置空。

过程：

1、比较list1->val和list2->val，如果list1小，这时list1的头结点，就将是新链表的头结点，合成链表中此时只有这一个元素，因此我们将head和tail都赋为list1，由于list1第一个节点比较完了，因此将list1走向下一个节点。list1=list1->next。

2、当比较到第二个元素时，如果此时list2->val小于list1->val，这时tail的next就要指向list2,tail->next = list2，list2也要继续走向list2的下一个元素，list2 = list2->next,tail也要继续向下走，要一直保证tail的next是空，因为tail要一直将list1和list2中较小的值链接起来。

3、就这样持续循环下去，当其中的某一个list链表走向空，也就是list==NULL时，合成的链表的尾结点tail直接链接到另外一个list链表即可，因为list1和list2均为升序链表，并且每次新合成链表只链接一个结点，因此list两个链表一定有先链接完和后链接完之分。

4、特殊情况：当list1或者list2有某一链表为空时，返回另一个链表

 if(list1==NULL) return list2;
 if(list2==NULL) return list1;

?

?(本题完)

?

?