首页 > 代码库 > LeetCode：Merge Two Sorted Lists

LeetCode：Merge Two Sorted Lists

2024-07-25 18:46:33   218人阅读

题目：Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

简单题，只要对两个链表中的元素进行比较，然后移动即可，只要对链表的增删操作熟悉，几分钟就可以写出来，代码如下：

 1 struct ListNode { 2     int val; 3     ListNode *next; 4     ListNode(int x):val(x), next(NULL) {} 5 }; 6  7 ListNode *GetLists(int n)    //得到一个列表 8 { 9     ListNode *l = new ListNode(0);10     ListNode *pre = l;11     int val;12     for (int i = 0; i < n; i ++) {13         cin >> val;14         ListNode *newNode = new ListNode(val);15         pre->next = newNode;16         pre = pre->next;17     }18     return l->next;19 }20 21 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)22 {23     assert (NULL != l1 && NULL != l2);24     if (NULL == l1 && NULL == l2)25         return NULL;26     if (NULL == l1 && NULL != l2) // !!要记得处理一个为空，另一个不为空的情况27         return l2;28     if (NULL != l1 && NULL == l2)29         return l1;30     31     ListNode *temp = new ListNode(0);32     temp->next = l1;33     ListNode *pre = temp;34 35     while(NULL != l1 && NULL != l2) {36         if (l1->val > l2->val) { //从小到大排列37             ListNode *next = l2->next;38             l2->next = pre->next;39             pre->next = l2;40             l2 = next;41         }        42         else {43             l1 = l1->next;44         }45         pre = pre->next;46     }47     if (NULL != l2) {48         pre->next = l2;49     }50     return temp->next;51 }

这其中要注意一点，即要记得处理一个链表为空，另一个不为空的情况，如{}, {0} -- > {0},当然上面的写法多少啰嗦了一些，可以简写。

LeetCode：Merge Two Sorted Lists


联系
我们