链表.md

反转链表

ListNode* reverse_list(ListNode* head){
        ListNode* dummy = nullptr;
        ListNode* cur = head;
        while(cur != nullptr){
            ListNode* tmp =cur->next;
            cur->next = dummy;
            dummy = cur;
            cur = tmp;
        }
        return dummy;
    }

快慢指针寻找中点

ListNode* find_middle_points(ListNode* head){
  	    ListNode* fast = head,* slow = head;
  	    while(fast->next != nullptr && fast->next->next != nullptr){
      	    slow = slow->next;
      	    fast = fast->next->next;
        }
  	    return slow;
    }

单增循环链表插入节点

Node* insert(Node* head, int insertVal) {
        if(head == nullptr){
            head  = new Node(insertVal);
            head->next = head;
            return head;
        }
        Node* cur = head;
        while( cur->next != head){
            if(cur->next->val<cur->val){
                if(cur->next->val >= insertVal) break;
                else if(cur->val<=insertVal) break;
            }
            if(cur->val <= insertVal && cur->next->val >= insertVal) break;
            cur = cur->next;
        }
        cur->next = new Node(insertVal,cur->next);
        return head;
    }

LRU缓存

//hashmap+双链表
struct DlinkNode{
    int key,value;
    DlinkNode* prev;
    DlinkNode* next;
    DlinkNode():key(0), value(0), prev(nullptr), next(nullptr){};
    DlinkNode(int _key, int _value):key(_key),value(_value),prev(nullptr) ,next(nullptr){};
};
class LRUCache {
private:
    int size = 0;
    unordered_map<int,DlinkNode*> m;
    int cap;
    DlinkNode* head;
    DlinkNode* tail;
public:
    void move_to_head(DlinkNode* node){
        del_node(node);
        add_to_head(node);
    }
    void add_to_head(DlinkNode* node){
        node->next = head->next;
        head->next->prev = node; 
        head->next = node;
        node->prev = head;
    }
    void del_node(DlinkNode* node){
        node->next->prev=node->prev;
        node->prev->next = node->next;
    }
    DlinkNode* del_tail(){
        DlinkNode* tmp = tail->prev;
        del_node(tmp);
        return tmp;
    }
    LRUCache(int capacity) {
        cap = capacity;
        head = new DlinkNode();
        tail = new DlinkNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if(!m.count(key)) return -1;
        DlinkNode* node = m[key];
        move_to_head(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if(m.count(key)){
            DlinkNode* node = m[key];
            node->value = value;
            move_to_head(node);
        }
        else{
            ++size;
            DlinkNode* node = new DlinkNode(key,value);
            add_to_head(node);
            m[key] = node;
            if(size > cap){
                DlinkNode* removed = del_tail();
                m.erase(removed->key);
                delete removed;
                --size;
            }
        }
    }
};

K个一组反转链表

#给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

解法1:模拟
每次k个一组反转，记录反转之前的pre和next，执行反转操作，再进行拼接
值得注意的是，在写反转函数时，此时需要dummy指针指向tail->next 而不是nullptr，
因为简单的反转链的尾部是nullptr，现在是tail->next

pair<ListNode*,ListNode*> reverse(ListNode* head, ListNode* tail){
  	ListNode* dummy = tail->next;
  	ListNode* cur = head;
  	while(dummy != tail){
      	ListNode* node = cur->next;
      	cur->next = dummy;
      	dummy = cur;
      	cur = node;
    }
  	return {tail, head};
}
ListNode* reverseKGroup(ListNode* head, int k){
  	ListNode* new head = new ListNode(-1,head);
  	ListNode* pre = newhead;
  	while(head){
      	ListNode* tail = pre;
      	for(int i=0;i<k;i++){
          	tail = tail->next;
          	if(!tail){
              	return newhead->next;
            }
        }
      	tie(head,tail) = reverse(head, tail);
      	pre->next = head;
      	pre = tail;
      	head = pre->next;
    }
  	return newhead->next;
}


解法2:递归
ListNode* reverseKGroup(ListNode* head, int k) {
       if(head==nullptr) return head;
       ListNode *tail=head;
       for(int i=0;i<k;i++){
           if(tail==nullptr) return head;
           tail=tail->next;
       }
       ListNode* pre=nullptr;
       ListNode* cur=head;
       while(cur!=tail){
           ListNode* next=cur->next;
           cur->next=pre;
           pre=cur;
           cur=next;
       }
       head->next=reverseKGroup(tail,k);
       return pre;
    }