[leetcode]: 21. Merge Two Sorted Lists

雨点打透心脏的1/2处 2022-06-15 02:42 269阅读 0赞

1.题目

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.
合并两个有序的列表

2.分析

遍历两个列表,每次将较小的节点加入到合并列表的尾部。

3.代码

  1. class Solution {
  2. public:
  3. //递归
  4. ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  5. if (l1 == NULL)
  6. return l2;
  7. if (l2 == NULL)
  8. return l1;
  9. ListNode* node = NULL;
  10. if (l1->val < l2->val){
  11. node = l1;
  12. node->next = mergeTwoLists(l1->next, l2);
  13. }
  14. else {
  15. node = l2;
  16. node->next = mergeTwoLists(l1, l2->next);
  17. }
  18. return node;
  19. }
  20. //迭代
  21. ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  22. if (l1 == NULL)
  23. return l2;
  24. if (l2 == NULL)
  25. return l1;
  26. ListNode* head = new ListNode(0);
  27. ListNode* tail = head;
  28. while (l1&&l2) {
  29. if (l1->val < l2->val){
  30. tail->next = l1;
  31. l1=l1->next;
  32. }
  33. else{
  34. tail->next = l2;
  35. l2=l2->next;
  36. }
  37. tail = tail->next;
  38. }
  39. tail->next = l1 ? l1 : l2;
  40. return head->next;
  41. }
  42. };

发表评论

表情:
评论列表 (有 0 条评论,269人围观)

还没有评论,来说两句吧...

相关阅读