如何高效合并两个已排序的链表至LeetCode？

本文共计600个文字，预计阅读时间需要3分钟。

将伪代码简化如下：

定义单链表节点结构struct ListNode { int val; struct ListNode *next;};

合并两个有序链表mergeTwoLists(ListNode *list1, ListNode *list2) { // ...}

力扣链接

依次比较,取小的尾插:

初步代码:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head = NULL,*tail = NULL; struct ListNode* cur1 = list1; struct ListNode* cur2 = list2; while(cur1 && cur2) { if(cur1->val<cur2->val) { if(head == NULL) { head = tail = cur1;//为空直接赋值 } else { tail->next = cur1; tail = tail->next; } cur1 = cur1->next; } else { if(head == NULL) { head = tail = cur2; } else { tail->next = cur2; tail = tail->next; } cur2 = cur2->next; } } if(cur2) { tail->next = cur2; } if(cur1) { tail->next = cur1; } return head; }

通过测试用例来看,当其中一个链表为空时,上面的代码不执行while循环,直接执行下面的if语句,而此时tail为空,所以出现了错误.

修改方法

1.直接判空返回(在声明前加入)

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1 == NULL)//判空返回 return list2;// if(list2 == NULL)// return list1;// struct ListNode* head = NULL,*tail = NULL; struct ListNode* cur1 = list1; struct ListNode* cur2 = list2; while(cur1 && cur2) { if(cur1->val<cur2->val) { if(head == NULL) { head = tail = cur1;//为空直接赋值 } else { tail->next = cur1; tail = tail->next; } cur1 = cur1->next; } else { if(head == NULL) { head = tail = cur2; } else { tail->next = cur2; tail = tail->next; } cur2 = cur2->next; } } if(cur2) { tail->next = cur2; } if(cur1) { tail->next = cur1; } return head; }

2.引用带哨兵卫的头结点(可以减少代码量,不存放有效数据)

哨兵位的头结点不存放有效数据,但是一直存在,所以不需要判空,需要开辟和释放空间

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* cur1 = list1; struct ListNode* cur2 = list2; struct ListNode* guard = NULL,*tail = NULL; guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); tail->next = NULL; while(cur1 && cur2) { if(cur1->val<cur2->val) { // if(head == NULL) // { // head = tail = cur1;//为空直接赋值 // } // else // { tail->next = cur1; tail = tail->next; // } cur1 = cur1->next; } else { // if(head == NULL) // { // head = tail = cur2; // } // else // { tail->next = cur2; tail = tail->next; // } cur2 = cur2->next; } } if(cur2) { tail->next = cur2; } if(cur1) { tail->next = cur1; } struct ListNode* head = guard->next;//存放哨兵位头结点的下一位,方便返回 free(guard); return head; }