Linked List

52. 21. Merge Two Sorted Lists

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

53. 141. Linked List Cycle

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

More,

1. How to get the length of the circle?

2. How to get the entry point of the circle?

54. Reverse Linked List

TODO

55. Middle of the Linked List

TODO

56. 146. LRU Cache

class LRUCache {
public:
    LRUCache(int capacity): cap(capacity), head(new Node(-1, -1)), tail(new Node(-1, -1)) {
        head->next = tail;
        head->prev = nullptr;
        tail->prev = head;
        tail->next = nullptr;
    }

    LRUCache(const LRUCache&) = delete; // disable copy
    LRUCache& operator=(const LRUCache&) = delete; // disable copy
    
    int get(int key) {
        if (m.find(key) != m.end()) {
            Node* curr = m[key];
            int ans = curr->val;
            
            deleteNode(curr);
            addNode(curr); // add to the first

            return ans;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (m.find(key) != m.end()) {
            Node* curr = m[key];
            m.erase(key);
            deleteNode(curr);
            delete curr;
        }

        if (m.size() == cap) {
            Node* last = tail->prev;
            m.erase(last->key);
            deleteNode(last);
            delete last;
        }

        addNode(new Node(key, value));
        m[key] = head->next;
    }

    ~LRUCache() {
        Node* d = head;
        while(d->next != nullptr) {
            Node* tmp = d->next;
            delete d;
            d = tmp;
        }
    }
private: 
    // private members of the nested classes are not visible from instances of the enclosing class
    class Node { 
    public:
        Node(int k, int v): key(k), val(v) {}     
    private:
        Node* prev;
        Node* next;
        int key;
        int val;  

        friend class LRUCache;
    };   

    int cap;
    unordered_map<int, Node*> m;
    Node* head;
    Node* tail;

    void addNode(Node* newNode) {
        Node* temp = head->next;
        newNode->next = temp;
        newNode->prev = head;
        temp->prev = newNode;
        head->next = newNode;
    } 

    void deleteNode(Node* delNode) {
        Node* prevv = delNode->prev;
        Node* nextt = delNode->next;
        prevv->next = nextt;
        nextt->prev = prevv;
    }
};

/**
 * 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);
 */