1.题目描述

题目链接：力扣21，合并两个有序链表

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

2.解题思路

方法1：

首先我们能够想到的就是遍历一遍数组，判断两个结点的大小，将数值小的结点放在前面，数值大的不断尾插在后面。是不是听着挺简单的？

具体实现：

我们可以创建两个空指针，head用来存放链表的头结点，tail用来遍历两条链表，将两条链表链接起来。

• 当某个链表为空时，我们可以直接返回另一条链表
• 当两个链表都不为空时，我们可以不断比较两条链表的大小，当 head 和 tail 为空时，我们将较小的结点同时赋给 head 和 tail。然后就是比较两条list的大小，将tail指向较小的结点，并将 tail 移到它的下一个结点位置。同时也将 list 指向它的下一个结点。
• 当一条链表遍历完后，由于链表是链接起来的，我们可以直接将尾指针 tail 指向另一条链表。这样两条链表就链接起来了。
• 最后我们再返回头结点 head 就可以了。

上代码：

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

方法2：

• 方法二和方法一差不多，我们可以创建一个带哨兵位的头结点，将小的结点不断尾插到这个带哨兵位的头节点后面，这样我们就不用判断链表是不是空链表了。

• 所谓带哨兵位的链表，就是一个附加的链表的节点，该节点作为第一个节点，它的值域并不存储任何东西，只是为了操作的方便引用的。

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