LeetCode.21.206(递归&回溯)

21.合并两个有序链表

好久之前写过，因为学习规划又写了一遍，这次用了递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
  public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (!l1) {
            return l2;
        }
        if (!l2) {
            return l1;
        }
        ListNode *l3;
        if (l1->val <= l2->val) {
            l3 = l1;
            l3->next = mergeTwoLists(l1->next, l2);
        } else {
            l3 = l2;
            l3->next = mergeTwoLists(l1, l2->next);
        }
        return l3;
        // 208/208 cases passed (4 ms)
        // Your runtime beats 92.89 % of cpp submissions
        // Your memory usage beats 46.24 % of cpp submissions (14.4 MB)
        //递归法,想办法不用l3空间复杂度还能降
        /*ListNode l3;
        ListNode *p3 = &l3;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                p3->next = l1;
                l1 = l1->next;
                p3 = p3->next;
            } else {
                p3->next = l2;
                l2 = l2->next;
                p3 = p3->next;
            }
        }
        p3->next = l1 ? l1 : l2;
        return l3.next;*/
        // 208/208 cases passed (12 ms)
        // Your runtime beats 48.07 % of cpp submissions
        // Your memory usage beats 99.03 % of cpp submissions (14.2 MB)
    }
};

206.反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
  public:
    ListNode *reverseList(ListNode *head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode *temp = reverseList(head->next);
        if (head) {
            ListNode *point = temp;
            while (point->next) {
                point = point->next;
            }
            point->next = head;
            point->next->next = nullptr;
        }
        return temp;
        // 28/28 cases passed (28 ms)
        // Your runtime beats 46.94 % of cpp submissions
        // Your memory usage beats 25.8 % of cpp submissions (8.2 MB)
    }
};