刷题笔记

【0】链表

① 反转链表

• 递归方法（从后向前）

  让当前节点的下一个节点指向自己，然后让当前节点指向空（将箭头反向）

  • 递归写法（分为四个部分）
    • 最前为触底条件，到什么情况停止递归
    • 后为深入时要完成的操作
    • 再为调用函数本身
    • 后为触底反弹后要完成的操作
  • 递归用时间换空间

class Solution {
public:
    vector<int> reverseBookList(ListNode* head) {
        vector<int> valInt;
        ListNode* tempNode = reverseNode(head);
        while(tempNode != nullptr)
        {
            valInt.push_back(tempNode->val);
            tempNode = tempNode->next;
        }
        return valInt;
    }
private:
    ListNode* reverseNode(ListNode* head)
    {
        if(head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode* tempNode = reverseNode(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tempNode;
    }
};

• 非递归方法（从前往后）

​ 让当前节点指向上一个节点

class Solution {
public:
    vector<int> reverseBookList(ListNode* head) {
        vector<int> valInt;
        ListNode* proNode = nullptr;
        while(head != nullptr)
        {
            ListNode* next = head->next;
            head->next = proNode;
            proNode = head;
            head = next;
        }
        while(proNode != nullptr)
        {
            valInt.push_back(proNode->val);
            proNode =  proNode->next;
        }
        return valInt;
    }
};

② 快慢指针

• 输出链表倒数第几位的节点，使用两个指针，一个在前面快，一个在后面慢，保持相等的间距，当前面的指针指向空时，后面的指针指向的就是要找的节点