LeetCode | 21. 合并两个有序链表
- 定义一个新链表，把小的结点尾插到新的链表
- 注意在插入新的链表中，1. 空链表，插入的节点就是链表的头节点和尾结点。2. 非空链表，插入的节点就是链表的新的尾结点，头结点不变
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1 == NULL) return list2; if(list2 == NULL) return list1; struct ListNode* newTail,*newHead; newHead = newTail = NULL; struct ListNode* cur1 = list1; struct ListNode* cur2 = list2; while(cur1 && cur2) { if(cur1->val<cur2->val) { //将cur1放入新的链表 if(newHead == NULL) { newHead = newTail = cur1; } else { newTail->next = cur1; newTail = newTail->next; } cur1 = cur1->next; } else { //将cur2放入新的链表 if(newHead == NULL) { newHead = newTail = cur2; } else { newTail->next = cur2; newTail = newTail->next; } cur2 = cur2->next; } } if(cur1) { newTail->next = cur1; } if(cur2) { newTail->next = cur2; } return newHead; }
- 大家可可以看到这个代码很长，很冗余
- 需要考虑新链表的头结点为空或者非空，所以导致这里的重复代码比较多
- 我们还有一个方法，创建一个带头单向不循环链表，后续就不需要考虑节点问题了
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1 == NULL) return list2; if(list2 == NULL) return list1; struct ListNode* cur1 = list1; struct ListNode* cur2 = list2; //创建一个带头单向不循环 struct ListNode* newTail,*newHead; newHead = newTail = (struct ListNode*)malloc(sizeof(struct ListNode)); while(cur1 && cur2) { if(cur1->val<cur2->val) { newTail->next = cur1; newTail = newTail->next; cur1 = cur1->next; } else { newTail->next = cur2; newTail = newTail->next; cur2 = cur2->next; } } if(cur1) { newTail->next = cur1; } if(cur2) { newTail->next = cur2; } //把动态开辟的空间释放掉 struct ListNode* tmp = newHead->next; free(newHead); return tmp; }
