完成日期：7月22日，7月23日

总结：

1. 注意传进来的参数，不是引用，那就直接利用，无需额外定义
2. 注意递归就是假装函数已经帮我做好了全部。这么去想

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) {
        ListNode* p1=l1, *p2=l2;
        ListNode* head, *p;
        
        if(!(p1||p2)) return nullptr;
        else if(!p1)  return p2;
        else if(!p2)  return p1;

        if(p1->val<=p2->val){
            head = p1;
            p1 = p1->next;
        }
        else{
            head = p2;
            p2=p2->next;
        }
        p = head;

        while(p2&&p1){
            if(p1->val<=p2->val){
                p->next = p1;
                p1=p1->next;
                p=p->next;
            }
            else{
                p->next = p2;
                p2=p2->next;
                p=p->next;
            }
        }
        if(p1) p->next=p1;
        else if(p2) p->next=p2;
        return head;
    }
};

// 官方：递归(好简洁呀！你仔细想想吧你)
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }else if(l2 == nullptr){
            return l1;
        }else if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }

//官方：迭代(好简洁呀！！！！！)
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *preHead = new ListNode(-1);
        ListNode *prev = preHead;
        while(l1!=nullptr && l2!=nullptr){
            if (l1->val < l2->val){
                prev->next = l1;
                l1 = l1->next;
            }else{
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        prev->next = l1==nullptr ? l2 : l1;
        return preHead->next;
    }

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 *res = new ListNode();
        ListNode *p1=head, *p2=head->next;
        while(p2){
            p1->next = res->next;
            res->next = p1;
            p1 = p2;
            p2 = p2->next;
        }
        p1->next = res->next;
        res->next = p1;
        return res->next;
    }
};

// 官方迭代（好简洁）
ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while(curr){
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;        
    }

 // 官方递归（有点厉害）
ListNode* reverseList(ListNode* head) {
        if(!head || !head->next){
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }