简介

链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。
它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

单向链表

struct node {
    int val;
    node *next;
};

双向链表

struct node {
    int val;
    node *prev;
    node *next;
};

题目与题解

141. 环形链表

难度：简单

标签：链表 双指针 哈希表

题目描述:
给你一个链表的头节点head，判断链表中是否有环。
细节描述：如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 如果链表中存在环 ，则返回true。否则，返回false。

题解

经典算法Floyd判圈算法(又称龟兔赛跑算法):

• 假想乌龟和兔子在链表上移动，兔子跑得快，乌龟跑得慢。当乌龟和兔子从链表上的同一个节点开始移动时，如果该链表中没有环，那么兔子将一直处于乌龟的前方并最终到达终点(链表结尾)；
  如果该链表中有环，那么兔子会先于乌龟进入环，并且一直在环内移动。等到乌龟进入环时，由于兔子的速度快，它一定会在乌龟走了一圈之前与乌龟相遇，即套了乌龟若干圈。

对于这道题目来说，就可以使用快慢指针的方式，慢指针每次移动一步，快指针每次移动两步。
初始时快慢指针都在head节点，slow和fast指针执行移动的循环，直到slow和fast指针再次相遇，此时即可证明链表存在环，否则链表无环。

c++

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

142. 环形链表II

难度：中等

标签：链表 双指针 哈希表

题目描述:
给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，则返回null。 不允许修改链表

题解

和上一道题目一样，继续使用快慢指针的方式，慢指针每次移动一步，快指针每次移动两步。
初始时快慢指针都在head节点，slow和fast指针执行移动的循环，直到slow和fast指针再次相遇。 假设从head节点走到in入环节点需要移动a步，slow和fast指针在节点meet处相遇，此时slow节点又移动b步，节点fast在环内移动 n * (b + c) + b 步，共移动 a + n * (b + c) + b 步，节点slow共移动 a + b 步。而fast走的步数又是slow的两倍，因此有

$$\begin{aligned} a + n \left( b + c \right) + b = 2 \left( a + b \right) \\ \Rightarrow \ &a = n \left( b + c \right) - b = \left( n - 1 \right) \left( b + c \right) + c \\ \end{aligned}$$

那么，如果此时slow和fast指针分别从head和meet节点开始走，当两个指针再次相遇时，slow刚好走了a步，fast绕着环走了(n-1)圈又走了c的步数，此时相遇在in节点，即可返回该节点。

c++

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) {
            return nullptr;
        }
        ListNode *slow, *fast;
        slow = 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;
    }
};

146. LRU 缓存

难度：中等

标签：双向链表 哈希表 设计

题目描述:
请你设计并实现一个满足LRU(最近最少使用)缓存约束的数据结构。 实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量capacity初始化LRU缓存
• int get(int key) 如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。
• void put(int key, int value) 如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。 函数get和put必须以O(1)的平均时间复杂度运行。

注

在双向链表的实现中，使用一个伪头部(dummy head)和伪尾部(dummy tail)标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

struct node {
    int key, value;
    node *prev, *next;
    node() : key(0), value(0), prev(nullptr), next(nullptr) {}
    node(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, node*> cache;
    node *head, *tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity) : capacity(_capacity), size(0){
        head = new node();
        tail = new node();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        node* cur = cache[key];
        moveToHead(cur);
        return cur->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            node* cur = new node(key, value);
            cache[key] = cur;
            insertNode(head, cur);
            ++size;
            if (size > capacity) {
                node* remo = tail->prev;
                deleteTail();
                cache.erase(remo->key);
                delete remo;
                --size;
            }
        }
        else {
            node* cur = cache[key];
            cur->value = value;
            moveToHead(cur);
        }

    }

    void deleteNode(node* cur) {
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;
    }
    void insertNode(node* pre, node* cur) {
        cur->next = pre->next;
        pre->next->prev = cur;
        pre->next = cur;
        cur->prev = pre;
    }
    void moveToHead(node* cur) {
        deleteNode(cur);
        insertNode(head, cur);
    }
    void deleteTail() {
        node *cur = tail->prev;
        deleteNode(cur);
    }
};
/**
 * 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);
 */

206. 反转链表

难度：简单

标签：链表 递归

题目描述:
给你单链表的头节点head，请你反转链表，并返回反转后的链表。

迭代法

依次将当前节点的指针指向前一个节点即可
由于节点没有引用前一个节点，需要存储前一个节点来进行连接

class Solution {
public:
    ListNode* pre = nullptr;
    ListNode* reverseList(ListNode* head) {
        while (head) {
            ListNode* nex = head->next;
            head->next = pre;
            pre = head;
            head = nex;
        }
        return pre;
    }
};

递归法

假设节点 i之后的其余部分链表已经被反转，那么只需要将节点 i的下一个节点指向i即可
需要注意的是需要将当前节点指向空

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