题目要求
方法1：使用头指针
思路
- 假设两个链表分别为l1和l2,l1和l2都是有序的
- 因为要 排成升序，把l1和l2指向的结点的较小的尾插到新链表
- 由于是尾插到新链表：为了方便，可以定义两个指针，一个新链表的头，一个指向新链表的尾
- 这里使用的是头指针的写法：
- 首先：我们应该提前把l1和l2中的较小结点，尾插下来当头结点，更新尾指针
- 然后l1和l2继续向后比较，找到把小的尾插下去，然后更新尾指针
- 因为总有一个链表先遍历完(走到空)，把另一个没有遍历完的链表直接链接到尾指针后面即可(因为：l1和l2都是有序的)
- 然后返回新链表的头指针即可
**注意：**如果其中一个链表一开始就是空，就返回另一个链表
图解
代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { //l1为空链表就返回l2 if(l1 == NULL) { return l2; } //l2为空链表就返回l1 if(l2 == NULL) { return l1; } //使用头指针 //定义头尾指针 struct ListNode* head = NULL,*tail = NULL; //先从l1和l2选一个小的下来作为头，排升序 if(l1->val < l2->val) { //头尾指针都要更新 head = l1; tail = l1; //l1更小，l1继续往后走 l1 = l1->next; } else { //头尾指针都要更新 head = l2; tail = l2; //l1小，l2继续往后走 l2 = l2->next; } //遍历比较 -如果有一个链表走完(空指针)就跳出循环 while(l1 && l2) { if(l1->val > l2->val ) { tail ->next = l2;//尾指针链接小的结点 tail = l2;//更新尾结点 l2 = l2->next;//小的结点的链表向后走 } else{ tail ->next = l1;//尾指针链接小的结点 tail = l1;//更新尾结点 l1 = l1->next;//小的结点的链表向后走 } } //有一个结束了-未知是哪个先结束->两个都判断 //下面的两个if判断，只进入一个 if(l1) { tail->next = l1;//尾指针链接没有比较完的链表 } else{ tail->next = l2;//尾指针链接没有比较完的链表 } return head;//返回新链表的头指针 }
方法2：使用哨兵位
思路
和上面方法1基本一致
- 假设两个链表分别为l1和l2,l1和l2都是有序的
- 使用了哨兵位，所以不需要先选一个下来当头结点
- 由于是尾插到新链表：为了方便，可以定义两个指针，一个新链表的头，一个指向新链表的尾
- 这里使用的是哨兵位的写法：
- 注意：哨兵位的next才是第一个结点，哨兵位不存储有效数据
- l1和l2从头开始向后比较，找到把小的尾插下去，然后更新尾指针
- 因为总有一个链表先遍历完(走到空)，把另一个没有遍历完的链表直接链接到尾指针后面即可(因为：l1和l2都是有序的)
- 然后返回新链表的头指针即可，返回的是head->next才是第一个结点
注意：最后哨兵位结点要释放掉
代码
/** * Definition for singly-linked list. * 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; } //使用哨兵位 struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* tail = head; //遍历比较 -如果有一个走完就跳出循环 while(l1 && l2) { if(l1->val > l2->val ) { tail->next =l2 ; tail = tail->next; l2 = l2->next; } else{ tail->next = l1; tail = tail->next; l1 = l1->next; } } //有一个结束了 if(l1) { tail->next = l1; } else{ tail->next = l2; } //保存第一个结点，防止释放掉哨兵位之后找不到 struct ListNode* tmp = head->next; //哨兵位结点要释放掉，然后置空 free(head); head = NULL; return tmp; }
