Leetcode hot 100（day 3）

反转链表

做法一：迭代法，只需要记录一下前面和后面的节点即可

这里没有null 要么是NULL 要么是nullptr

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev=NULL;
        ListNode* cur=head;
        while(cur!=NULL)
        {
            ListNode* next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }
};

做法二。递归法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next)
        {
            return head;
        }
        ListNode* newhead=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return newhead;
        
    }
};

回文链表

做法一：无脑暴力法，先遍历一遍顺便翻转链表，然后再反着遍历一遍就可以了。

写完才发现，可以直接遍历数组，没有必要反转链表

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        queue<int> ans;
        ListNode*prev=nullptr;
        ListNode*cur=head;
        while(cur!=nullptr)
        {
             ListNode*nextnode=cur->next;
             cur->next=prev;
             prev=cur;
             cur=nextnode;
             ans.emplace(prev->val);
        }
        while(prev!=nullptr)
        {
            if(prev->val!=ans.front())return false;
            ans.pop();
            prev=prev->next;
        }
        return true;
    }
};

做法二：真的太巧妙了这个想法，利用递归。这个就感觉很深入递归的本质了。先一层层往下递归，如果最后一层和保存在外部的变量值相同，那么就把fp=fp->next。同时递归返回上一层，相当于倒退。但空间开的更大了没办法

class Solution {
    ListNode* fp;
public:
    bool reverselist(ListNode* cur)
    {
        if(cur!=nullptr)
        {
            if(!reverselist(cur->next))return false;
            if(cur->val!=fp->val)return false;
            fp=fp->next;
        }
        return true;
    }
    bool isPalindrome(ListNode* head) {
        fp=head;
        return reverselist(fp);
    }
};

做法三：只需要O(1)空间。首先利用快慢指针，找到中间部分的指针，然后把后半段链表翻转。接着两边同时遍历直到后半段指针为nullptr即可

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==nullptr)return true;
        ListNode *fp=endof(head);
        ListNode *sp=reverselist(fp->next);
        ListNode* p1=head;
        ListNode *p2=sp;
        bool result=true;
        while(result&&p2!=nullptr)
        {
            if(p1->val!=p2->val)
            {
                result=false;
                break;
            }
            p1=p1->next;
            p2=p2->next;
        }
        return result;
    }
    ListNode* reverselist(ListNode* head)
    {
        ListNode* prev=nullptr;
        ListNode* cur=head;
        while(cur!=nullptr)
        {
            ListNode* nextcur=cur->next;
            cur->next=prev;
            prev=cur;
            cur=nextcur;
        }
        return prev;
    }
    ListNode* endof(ListNode *head)
    {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast->next!=nullptr&&fast->next->next!=nullptr)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
};

环形链表

做法一：常规开哈希，遍历一遍即可

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> mp;
        while(head!=nullptr)
        {
            if(mp.count(head))return true;
            mp.insert(head);
            head=head->next;
        }
        return false;
    }
};

做法二;十分巧妙地快慢指针。快指针走两步，慢指针走一步。注意初始的时候要先特判head为空和head->next为空。并且因为循环的终止条件是两者相等，所以要初始的时候让快指针处于head->next。如果有环，一定会套圈的

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr||head->next==nullptr)return false;
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(slow!=fast)
        {
            if(fast==nullptr||fast->next==nullptr)return false;
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
    }
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr||head->next==nullptr)return false;
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast!=nullptr)
        {
            slow=slow->next;
            if(fast->next==nullptr)return false;
            fast=fast->next->next;
            if(slow==fast)return true;
        }
        return false;
    }
};

环形链表II

做法一：依旧哈希

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*>mp;
        while(head!=nullptr)
        {
            if(mp.count(head))return head;
            mp.insert(head);
            head=head->next;
        }
        return nullptr;
    }
};

做法二：使用快慢指针

在这里代码一定要注意 要判断fast->next是否为nullptr

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow=head,*fast=head;
        while(fast!=nullptr)
        {
            slow=slow->next;
            if(fast->next==nullptr)return nullptr;
            fast=fast->next->next;
            if(slow==fast)
            {
                ListNode* cur=head;
                while(cur!=slow)
                {
                    cur=cur->next;
                    slow=slow->next;
                }
                return cur;
            }
        }
        return nullptr;
    }
};

合并两个有序链表

做法一：最容易想到的迭代做法，其实就和合并两个有序数组是一个思路

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* prehead=new ListNode(-1);
        ListNode*prev=prehead;
        while(list1!=nullptr&&list2!=nullptr)
        {
            if(list1->val<list2->val)
            {
                prev->next=list1;
                list1=list1->next;
            }
            else
            {
                prev->next=list2;
                list2=list2->next;
            }
            prev=prev->next;
        }
        prev->next=list1==nullptr?list2:list1;
        return prehead->next;
    }
};

做法二：优雅的递归，虽然空间不太优雅，但写起来很好

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;
        }
    }
};

两数相加

做法：其实就和当初学的高精度加法大差不差，从最低位开始，由于没有办法知道链表的长度，所以循环就一直循环到两个链表都为nullptr才结束。如果其中一方为空，那么就不移动，并且设为0.最后不要忘记进位也要设节点

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head=nullptr,*tail=nullptr;
        int carry=0;
        while(l1||l2)
        {
            int n1=l1?l1->val:0;
            int n2=l2?l2->val:0;
            int sum=n1+n2+carry;
            if(!head)
            {
                head=tail=new ListNode(sum%10);
            }
            else
            {
                tail->next=new ListNode(sum%10);
                tail=tail->next;
            }
            carry=sum/10;
            if(l1)l1=l1->next;
            if(l2)l2=l2->next;
            if(carry)tail->next=new ListNode(carry);
        }
        return head;
    }
};

删除链表的倒数第N个节点

做法一：首先，这种题因为有可能删除头节点，所以必须创建一个哨兵节点指向头节点，并且要记得new之后一定要有delete（释放指针所指向区域的内存），不然运行时间会有差异。然后用vector或者用stack存一下节点就可以了

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head->next==nullptr)return nullptr;
        ListNode *prenode=new ListNode(-1);
        prenode->next=head;
        vector<ListNode*> vec;
        ListNode* cur=head;
        vec.emplace_back(prenode);
        while(cur!=nullptr)
        {
            vec.emplace_back(cur);
            cur=cur->next;
        }
        ListNode* node=vec[vec.size()-n-1];
        node->next=node->next->next;
        ListNode* ans=prenode->next;
        delete prenode;
        return ans;
    }
};

 做法二：使用双指针，快慢指针在链表中十分重要。fast比slow快n个身位，这样当快指针为nullptr的时候，slow指针就指向要被删除的节点，所以可以把slow指向哨兵节点，这样就能做了。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* pre=new ListNode(0,head);
        ListNode* fast=head;
        ListNode* slow=pre;
        while(n--)fast=fast->next;
        while(fast)
        {
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        ListNode* ans=pre->next;
        delete pre;
        return ans;
    }
};

当然也可以遍历两次，这里就不给出代码了，比较简单

两两交换链表中的节点 

做法一：迭代，还是得哨兵节点，没有的话不太好做。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* pre=new ListNode(0);
        pre->next=head;
        ListNode* temp=pre;
        while(temp->next!=nullptr&&temp->next->next!=nullptr)
        {
            ListNode* node1=temp->next;
            ListNode* node2=temp->next->next;
            temp->next=node2;
            node1->next=node2->next;
            node2->next=node1;
            temp=node1;
        }
        ListNode *ans=pre->next;
        delete pre;
        return ans;
    }
};

做法二：递归，简洁优雅

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr||head->next==nullptr)return head;
        ListNode* newhead=head->next;
        head->next=swapPairs(newhead->next);
        newhead->next=head;
        return newhead;
    }
};

k个一组翻转链表 

做法：一组组翻转链表即可，还是要创建哨兵，并且要判断是否剩余还有k个能进行翻转

class Solution {
public:
    pair<ListNode*,ListNode*>reverselist(ListNode* head,ListNode* tail)
    {
        ListNode* prev=nullptr;
        ListNode* p=head;
        while(prev!=tail)
        {
            ListNode* nex=p->next;
            p->next=prev;
            prev=p;
            p=nex;
        }
        return {tail,head};
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* pre=new ListNode(0,head);
        ListNode *prev=pre;
        while(head)
        {
            ListNode* tail=prev;
            for(int i=0;i<k;i++)
            {
                tail=tail->next;
                if(!tail)return pre->next;
            }
            ListNode* nex=tail->next;
            pair<ListNode*,ListNode*>result=reverselist(head,tail);
            head=result.first;
            tail=result.second;
            prev->next=head;
            tail->next=nex;
            prev=tail;
            head=tail->next;
        }
        return pre->next;
    }
};

随机链表的复制

做法一：哈希+递归。有一个问题就是，如果random回去了，那么如何识别，自家random呢。所以可以用哈希表在head和newhead两个链表间做一个映射。如果哈希映射存在，那么说明random到的节点不会有后续变化了，否则，要创造一个节点，并且继续往下递归。

class Solution {
public:
    unordered_map<Node*,Node*> mp;
    Node* copyRandomList(Node* head) {
        if(head==nullptr)return nullptr;
        if(!mp.count(head))
        {
            Node* newhead=new Node(head->val);
            mp[head]=newhead;
            newhead->next=copyRandomList(head->next);
            newhead->random=copyRandomList(head->random);
        }
        return mp[head];
    }
};

做法二：不用哈希表，而是在原本的链表之间插入节点

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = node->next;
            nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
        }
        Node* headNew = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* nodeNew = node->next;
            node->next = node->next->next;
            nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
        }
        return headNew;
    }
};

排序链表

做法一：归并排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head,nullptr);
    }
    ListNode* sortList(ListNode* head,ListNode* tail)
    {
        if(head==nullptr)return head;
        if(head->next==tail)
        {
            head->next=nullptr;
            return head;
        }
        ListNode* slow=head,*fast=head;
        while(fast!=tail)
        {
            slow=slow->next;
            fast=fast->next;
            if(fast!=tail)fast=fast->next;
        }
        ListNode* mid=slow;
        return merge(sortList(head,mid),sortList(mid,tail));
    }
    ListNode* merge(ListNode* head1,ListNode* head2)
    {
        ListNode* prev=new ListNode(0);
        ListNode* temp=prev,*temp1=head1,*temp2=head2;
        while(temp1!=nullptr&&temp2!=nullptr)
        {
            if(temp1->val<=temp2->val)
            {
                temp->next=temp1;
                temp1=temp1->next;
            }
            else
            {
                temp->next=temp2;
                temp2=temp2->next;
            }
            temp=temp->next;
        }
        if(temp1!=nullptr)temp->next=temp1;
        else if(temp2!=nullptr)temp->next=temp2;
        ListNode* ans=prev->next;
        delete prev;
        return ans;
    }
    
};

合并K个升序链表

做法一：一个个合并过去即可

class Solution {
public:
    ListNode* merge(ListNode* l1,ListNode* l2)
    {
        if(l1==nullptr)return l2;
        if(l2==nullptr)return l1;
        ListNode* prev=new ListNode(0),*cur=prev;
        while(l1!=nullptr&&l2!=nullptr)
        {
            if(l1->val<l2->val)
            {
                cur->next=l1;
                l1=l1->next;
            }
            else
            {
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        cur->next=l1==nullptr?l2:l1;
        cur=prev->next;
        delete prev;
        return cur;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans=nullptr;
        for(int i=0;i<lists.size();i++)ans=merge(ans,lists[i]);
        return ans;
    }
};

做法二:归并合并

做法三：优先队列

class Solution {
public:
    struct node
    {
        int val;
        ListNode *ptr;
    };
    struct cmp
    {
        bool operator()(const node& a,const node& b)const{
            return a.val>b.val;
        }
    };
    priority_queue<node,vector<node>,cmp> q;
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for(auto no:lists)
        {
            if(no)q.push({no->val,no});
        }
            ListNode *prev=new ListNode(0),*cur=prev;
            while(!q.empty())
            {
                auto f=q.top();
                q.pop();
                cur->next=f.ptr;
                cur=cur->next;
                if(f.ptr->next!=nullptr)q.push({f.ptr->next->val,f.ptr->next});
            }
            
        cur=prev->next;
            delete prev;
            return cur;
    }
};

LRU缓存

做法：有点麻烦，首先需要建立哈希映射。其次需要建立一个双向链表。链表的节点就是自定义类，，里面存储了key和对应的value，key可以映射到这个节点上面。LRU通过链表中位置来踢出

struct DLinkedNode
{
    int key,value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode():key(0),value(0),prev(nullptr),next(nullptr){}
    DLinkedNode(int key,int value):key(key),value(value),prev(nullptr),next(nullptr){}
};
class LRUCache {
public:
    unordered_map<int,DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;
    void addtohead(DLinkedNode* node)
    {
        node->prev=head;
        node->next=head->next;
        head->next->prev=node;
        head->next=node;
    }
    void removenode(DLinkedNode* node)
    {
        node->prev->next=node->next;
        node->next->prev=node->prev;
    }
    void movetohead(DLinkedNode* node)
    {
        removenode(node);
        addtohead(node);
    }
    DLinkedNode* removetail()
    {
        DLinkedNode* node=tail->prev;
        removenode(node);
        return node;
    }
    LRUCache(int capacity):capacity(capacity),size(0) {
        head=new DLinkedNode();
        tail=new DLinkedNode();
        head->next=tail;
        tail->prev=head;
        
    }
    
    int get(int key) {
        if(!cache.count(key))return -1;
        DLinkedNode* node=cache[key];
        movetohead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if(!cache.count(key))
        {
            DLinkedNode* node=new DLinkedNode(key,value);
            cache[key]=node;
            addtohead(node);
            size++;
            if(size>capacity)
            {
                DLinkedNode* removed=removetail();
                cache.erase(removed->key);
                delete removed;
                --size;
            }
        }
        else
        {
            DLinkedNode* node=cache[key];
            node->value=value;
            movetohead(node);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

二叉树的中序遍历

做法一：递归

class Solution {
public:
    void tree(TreeNode* node,vector<int>& vec)
    {
        if(node==nullptr)return;
        tree(node->left,vec);
        vec.push_back(node->val);
        tree(node->right,vec);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> vec;
        tree(root,vec);
        return vec;
    }
};

做法二：迭代

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> vec;
        stack<TreeNode*> s;
        while(root!=nullptr||!s.empty())
        {
            while(root!=nullptr)
            {
                s.push(root);
                root=root->left;
            }
            root=s.top();
            s.pop();
            vec.push_back(root->val);
            root=root->right;
        }
        return vec;
    }
};

做法三：morris遍历算法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *predecessor=nullptr;
        while(root!=nullptr)
        {
            if(root->left!=nullptr)
            {
                predecessor=root->left;
                while(predecessor->right!=nullptr&&predecessor->right!=root)
                {
                    predecessor=predecessor->right;
                }
                if(predecessor->right==nullptr)
                {
                    predecessor->right=root;
                    root=root->left;
                }
                else
                {
                    res.push_back(root->val);
                    predecessor->right=nullptr;
                    root=root->right;
                }
            }
            else{
                res.push_back(root->val);
                root=root->right;
            }
        }
        return res;
    }
};

二叉树最大深度

做法：递归 迭代都可以

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==nullptr)return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};