如何将两个有序链表巧妙合并成一个长尾词？

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

力扣链表合并+依次数比较，取小的尾插：初步代码：/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */int compare(struct ListNode *list1, struct ListNode *list2) { return list1->val - list2->val;}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode dummy; struct ListNode *current=&dummy; while (list1 && list2) { if (compare(list1, list2) next=list1; list1=list1->next; } else { current->next=list2; list2=list2->next; } current=current->next; } current->next=list1 ? list1 : list2; return dummy.next;}

力扣链接

依次比较,取小的尾插:

初步代码:

/** * 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; }