Algorithms & Data Structures : Linked-List Problems

Problem

LeetCode : 146. LRU Cache
[linked list]

LeetCode 2326. Spiral Matrix IV
[linked list]

LeetCode 2487. Remove Nodes From Linked List
[Linked-List]

— — — — —

LeetCode : 141. Linked List Cycle

LeetCode : 2. Add Two Numbers

LeetCode : 460. LFU Cache

LeetCode : 146. LRU Cache

使用 doubly linked list 去記錄所有被丟進 hash table 的節點。

每當一個 key 被 put 或是 get 的時候，就將該節點丟到 doubly linked list 的最尾端。如此一來，該 doubly linked list 的最頭端就是 LRU 的 key。

typedef struct Node Node;
struct Node{
    int key;
    int val;
    Node *prev;
    Node *next;
};
class LRUCache {
public:
    
    int c;
    int nowc;
    Node *head;
    Node *tail;
    unordered_map<int, Node *> um;
    
    LRUCache(int capacity) {  
        c = capacity;
        nowc = 0;
        
        head = new Node();
        head->key = -1;
        head->val = -1;
        tail = new Node();
        tail->key = -2;
        head->val = -2;
        
        head->next = tail;
        head->prev = NULL;
        tail->next = NULL;
        tail->prev = head;
    }
    
    int get(int key) {
        if(um.find(key) == um.end()) {
            return -1;
        }
        
        Node *nown  = um[key];
        Node *prevn = nown->prev;
        Node *nextn = nown->next;
            
        // delete Node
        prevn->next = nextn;
        nextn->prev = prevn;
            
        // insert Node
        prevn = tail->prev;
        nextn = tail;
            
        prevn->next = nown;
        nextn->prev = nown;
        nown->prev = prevn;
        nown->next = nextn;
        
        return um[key]->val;
    }
    
    void put(int key, int value) {
        if(um.find(key) == um.end()) {
            if(nowc == c) {
                // delete old Node
                Node *nown  = head->next;
                Node *prevn = head;
                Node *nextn = nown->next;
                                
                prevn->next = nextn;
                nextn->prev = prevn;
                um.erase(nown->key);
                //delete(nown);
            } else {
                nowc++;
            }
            
            Node *nown = new Node();
            nown->val = value;
            nown->key = key;
                
            um[key] = nown;
                
            //insert Node
            Node *prevn = tail->prev;
            Node *nextn = tail;
                
            prevn->next = nown;
            nextn->prev = nown;
            nown->prev = prevn;
            nown->next = nextn;
            
        } else {
            Node *nown  = um[key];
            Node *prevn = nown->prev;
            Node *nextn = nown->next;
            
            // update value
            nown->val = value;
            
            // delete Node
            prevn->next = nextn;
            nextn->prev = prevn;
            
            // insert Node
            prevn = tail->prev;
            nextn = tail;
            
            prevn->next = nown;
            nextn->prev = nown;
            nown->prev = prevn;
            nown->next = nextn;
        }
    }
};

LeetCode 2326. Spiral Matrix IV

/**
 * 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 {
private:
    int direc = 0;
    int X[4] = { 0, 1, 0, -1 };
    int Y[4] = { 1, 0, -1, 0 };
    
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> res = vector<vector<int>>(m, vector<int>(n, -1));
        
        int x = 0;
        int y = 0;
        for(ListNode *i = head;i != NULL;i = i->next) {
            res[x][y] = i->val;
            
            int newx = x + X[direc];
            int newy = y + Y[direc];
            if(newx < 0 || newx >= m ||
               newy < 0 || newy >= n ||
               -1 != res[newx][newy]) {
                direc++;
                direc %= 4;
            }
            
            x = x + X[direc];
            y = y + Y[direc];
        }
        
        return res;
    }
};

LeetCode 2487. Remove Nodes From Linked List

// TODO : 效能太差了
/**
 * 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* removeNodes(ListNode* head) {
        vector<ListNode *> v;
        vector<ListNode *> v2;
        for(ListNode *i = head;i != NULL;i = i->next) {
            v.push_back(i);
        }
        int maxVal = INT_MIN;
        for(int i = v.size() - 1;i >= 0;i--) {
            if(v[i]->val >= maxVal) {
                v2.push_back(v[i]);
                maxVal = v[i]->val;
            } else {
                v[i]->next = NULL;
            }
        }

        for(int i = v2.size() - 1;i >= 1;i--) {
            v2[i]->next = v2[i - 1];
        }

        return v2.back();
    }
};