# LeetCode: 21. 合并两个有序链表¶

## 1、题目描述¶

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



## 2.1 向前判断¶

​ 设置头指针和临时指针

/**
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// 返回用的头指针，指向数据小的元素的头元素
if (l1 == NULL || l2 == NULL) {
if (l1 == NULL) {

} else {
}
}

head = l1->val > l2->val ? l2 : l1;
if (l1->val > l2->val) {
l2 = l2->next;
} else {
l1 = l1->next;
}

while (l1 != NULL || l2 != NULL) {
if (l1 != NULL && l2 == NULL) {
temp->next = l1;
break;
} else if (l1 == NULL && l2 != NULL) {
temp->next = l2;
break;
} else {
if (l1->val > l2->val) {
temp = temp->next = l2;
l2 = l2->next;

} else {
temp = temp->next = l1;
l1 = l1->next;
}
}
}

}


## 2.2 递归法¶

/**
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
if (l1 == NULL){
return l2;
}
if (l2 == NULL){
return l1;
}
if (l1->val < l2->val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}else{
l2->next = mergeTwoLists(l2->next,l1);
return l2;
}
}