【算法速刷(8/100)】LeetCode —— 21.合并两个有序链表

使用两个指针顺序遍历两个链表，每次都将最小值的那个加到结果链表上，最后如果两个链表不一样长，就将剩下的接到结果后面

无头结点

 无头结点的情况下，处处都需要进行判空，将初次赋值和其他时候分为两个情况，会比较长

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//通过两个指针交替前进每次都对比并选择最小的节点放在结果节点上，完成遍历ListNode* head = nullptr, *p = nullptr;while(list1 && list2){if(list1->val < list2->val){if(!head){head = list1;p = list1;}else{p->next = list1;p = p->next;}list1 = list1->next;}else{if(!head){head = list2;p = list2;}else{p->next = list2;p = p->next;}list2 = list2->next;}}if(list1){if(!head)return list1;p->next = list1;}if(list2){if(!head)return list2;p->next = list2;}return head;}

有头结点

有头结点的时候，无需判断首次赋值，可以节省许多的代码行数和判断

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* head = new ListNode(-1);ListNode* pre = head;while(l1 && l2){if(l1->val < l2->val){pre->next = l1;l1 = l1->next;}else{pre->next = l2;l2 = l2->next;}pre = pre->next;}pre->next = l1 == nullptr ? l2 : l1;return head->next;}