首页 > 代码库 > leetcode - Merge Two Sorted Lists

leetcode - Merge Two Sorted Lists

2024-07-10 03:46:05   213人阅读

题目：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、合并两个有序链表，一般就是采用归并的方法，分别设置一个指针用于遍历链表，然后挨个比较节点大小，将小的那个节点作为新链表的下一个节点，然后让小节点的指针向后走一步，直到某个链表走完

2、当某个链表走完，则将另外一个链表的剩余部分接到新链表的后面就行了

代码：

 1 #include <stddef.h> 2  3 struct ListNode 4 { 5     int val; 6     ListNode *next; 7     ListNode(int x) : val(x), next(NULL) {}; 8 }; 9 10 class Solution11 {12 public:13     ListNode* mergeTwoLists(ListNode *l1, ListNode *l2)14     {15         //若l1或者l2为空16         if (!l1)17         {18             return l2;19         }20         if (!l2)21         {22             return l1;23         }24 25         ListNode *cur_l1 = l1;26         ListNode *cur_l2 = l2;27         ListNode *head_new = NULL;28         ListNode *cur_new = NULL;29 30         while (cur_l1 && cur_l2)31         {32             if (cur_l1->val <= cur_l2->val)33             {34                 if (!cur_new)35                 {36                     head_new = cur_new = cur_l1;37                 }38                 else39                 {40                     cur_new->next = cur_l1;41                     cur_new = cur_new->next;42                 }43                 cur_l1 = cur_l1->next;44             }45             else46             {47                 if (!cur_new)48                 {49                     head_new = cur_new = cur_l2;50                 }51                 else52                 {53                     cur_new->next = cur_l2;54                     cur_new = cur_new->next;55                 }56                 cur_l2 = cur_l2->next;57             }58         }59 60         if (!cur_l1)61         {62             while (cur_l2)63             {64                 cur_new->next = cur_l2;65                 cur_new = cur_new->next;66                 cur_l2 = cur_l2->next;67             }68         }69 70         if (!cur_l2)71         {72             while (cur_l1)73             {74                 cur_new->next = cur_l1;75                 cur_new = cur_new->next;76                 cur_l1 = cur_l1->next;77             }78         }79 80         return head_new;81     }82 };83 84 int main()85 {86     return 0;87 }
View Code

 

网上基本都是这个归并的思路，属于比较基础的题目。


联系
我们