算法（三）--链表

链表

tip：链表旋转操作如果是自己的size整数倍，等于没有操作。所以需要先把旋转次数对size取余。 time %= size

LRU缓存机制 Leetcode 146

使用双向列表和哈希表：

• 双链表存储一个节点被使用（get或者put）的时间戳，且按最近使用时间从左到右排好序，最先被使用的节点放在双链表的第一位，因此双链表的最后一位就是最久未被使用的节点；
• 哈希表存储key和对应的节点的地址，通过key可以在O(1)时间内找到对应的节点。

一般希望在O(1)时间内find内存位置的一般需要哈希表，以空间换时间。

注意：双链表的节点结构要保留key值，方便直接根据最右边的节点找到哈希表中对应的key值，然后删除哈希表中的value值。

class LRUCache {
public:
    // double forward list
    struct Node {
        Node* pre;
        Node* next;
        // key是哈希表的key
        int key_, val_;
        Node(int key, int val)
            : key_(key), val_(val), pre(nullptr), next(nullptr) {};
    } *L, *R;
    int n;
    unordered_map<int, Node*> map;

    // insert
    void insert(Node* node) {
        node->pre = L;
        node->next = L->next;
        L->next->pre = node;
        L->next = node;
    }

    // remove
    void remove(Node* node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1, -1), R = new Node(-1, -1);
        L->next = R;
        R->pre = L;
    }

    int get(int key) {
        if (map.count(key) == 0)
            return -1;
        Node* node = map[key];
        remove(node);
        insert(node);
        return node->val_;
    }

    void put(int key, int value) {
        if (map.count(key) > 0) {
            Node* replace = map[key];
            remove(replace);
            Node* node = new Node(key, value);
            map[key] = node;
            insert(node);
        } else {
            if (map.size() == n) {
                Node* old = R->pre;
                remove(old);
                map.erase(old->key_);
                delete old;
            }
            Node* node = new Node(key, value);
            map[key] = node;
            insert(node);
        }
    }
};

快慢指针检测有环链表环开始位置

算法思想：用两个指针，slow每次移动一步，fast每次移动两步，当fast到链表尾时，如果slow追上fast，说明存在环。此时将slow移至表头，快慢指针都同时移动一步，下一次相遇时，就是环产生的地方。

// 检测环的起始位置
ListNode* detectCycle(ListNode* head) {
    if (!head || !head->next) return nullptr;

    ListNode* slow = head;
    ListNode* fast = head;

    // 检测是否有环
    while (fast && fast->next) {
        slow = slow->next;         // 慢指针移动一步
        fast = fast->next->next;  // 快指针移动两步
        if (slow == fast) {       // 快慢指针相遇，说明有环
            // 找到环的起始位置
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow; // 返回环的起始节点
        }
    }

    return nullptr; // 如果没有环
}

随机链表的赋值

关键点在于如何通过原来的节点找到新复制的节点，这里用哈希表存储原节点和新节点的对应关系。两遍遍历链表，第一遍遍历原链表，进行深拷贝和建立原节点和新节点的对应关系；第二遍同时遍历原链表和新链表，把原链表的random对应的新节点赋值给新链表的random。

旋转数组

向右移动k个位置，也就是向左移动n-k+1个位置，向左移动比较好处理，只用将头节点移到尾部，不用去找尾节点

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* dummy = new ListNode(0, head);
        ListNode* cur = head;
        int sum = 0;
        while (cur->next != nullptr) {
            cur = cur->next;
            sum++;
        }
        sum++;
        k %= sum;
        ListNode* last = cur;
        ListNode* newhead = head;
        ListNode* pre = dummy;
        for (int i = 0; i < sum-k; i++) {
            pre = pre->next;
            newhead = newhead->next;
        }

        last->next = dummy->next;
        dummy->next = pre->next;
        pre->next = nullptr;

        return dummy->next;
    }
};

分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。

思想：维护两个链表，一个链表储存小于x的节点，一个链表储存大于等于x的节点，最后将两个链表连接起来。

    ListNode* partition(ListNode* head, int x) {
        ListNode* small = new ListNode(-1, nullptr);
        ListNode* large = new ListNode(-1, nullptr);
        ListNode* dummys = small;
        ListNode* dummyl = large;

        ListNode* cur = head;
        while(cur) {
            if(cur->val < x) {
                small->next = cur;
                small = small->next;
            }
            else {
                large->next = cur;
                large = large->next;
            }
            cur = cur->next;
        }
        large->next = nullptr;
        small->next = dummyl->next;
        return dummys->next;
    }

千万注意，最后要将large的next置为nullptr，否则会出现环。