LeetCode 21.合并两个有序链表(C++)

链表(C++)"/>

LeetCode 21.合并两个有序链表(C++)

题目地址：力扣

解法1：递归

写递归主要就是解决三个问题：

1、当前层我要干什么？

        答：需要把两个链中较小的那个节点的next指向下一层递归的结果

2、结束的边界条件是什么？

        答：任意一个链为空

3、我需要返回什么？

        答：若未触发边界条件，将当前处理的节点返回给上层。若触发边界条件，返回不为空的那个链。

代码如下：

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {// 这里是边界条件if (list1 == nullptr)return list2;else if (list2 == nullptr)return list1;// 这里是分情况进行递归else if (list1->val < list2->val){// 干当前层需要干的事情list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}}
};

解法2：迭代

迭代的方法就是先设置一个哨兵节点来防止一些边界情况。

然后进行循环，只要不满足循环退出的条件，就一直在两条链之间进行穿针引线，最后将两条链的节点穿在一条线上，返回哨兵节点的next就结束了

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode newHead = ListNode(0); // 先设置一个哨兵节点ListNode *pre = &newHead;while(true){    // 跳出循环的条件是两条链中一条为空的情况if (list1 == nullptr){pre->next = list2;break;}else if (list2 == nullptr){pre->next = list1;break;}else{    // 都不为空，那么就把pre的next指向较小的节点，pre再移动到其next，然后把较小节点所在链的指针向后移动if (list1->val > list2->val){pre->next = list2;pre = pre->next;list2 = list2->next;} else {pre->next = list1;pre = pre->next;list1 = list1->next;}}}return newHead.next;}
};

Accepted

• 208/208 cases passed (8 ms)
• Your runtime beats 59.34 % of cpp submissions
• Your memory usage beats 29.81 % of cpp submissions (14.4 MB)