Day 1 知识点：链表

知识

2.1.1 结构

typedef struct student{
  char name[20];
  char sex;
  int age;
}Student;

Student studA;

2.3.1 指针

• &取地址运算符
• *间接引用运算符

指针定义和运算

自引用结构

2.3.2 单链表

单链表结构

习题

21. 合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/

• 递归
• 链表

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

思路

我们直接将以上递归过程建模，同时需要考虑边界情况。

如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。

否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。

如果两个链表有一个为空，递归结束。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {//2.1.1 结构
 *     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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

146. LRU 缓存

题目

示例

代码

https://leetcode-cn.com/problems/lru-cache/

• 设计
• 哈希表
• 链表
• 双向链表

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

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

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {//对于 get 操作，
        if (!cache.count(key)) {//首先判断 key 是否存在：
            return -1;//如果 key 不存在，则返回 -1；
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];//如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，
        moveToHead(node);//并将其移动到双向链表的头部，
        return node->value;//最后返回该节点的值。
    }
    
    void put(int key, int value) {//对于 put 操作，
        if (!cache.count(key)) {//首先判断 key 是否存在：
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);//如果 key 不存在，使用 key 和 value 创建一个新的节点，
            // 添加进哈希表
            cache[key] = node;//并将 key 和该节点添加进哈希表中。
            // 添加至双向链表的头部
            addToHead(node);//在双向链表的头部添加该节点，
            ++size;
            if (size > capacity) {//然后判断双向链表的节点数是否超出容量，如果超出容量，
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();//则删除双向链表的尾部节点，
                // 删除哈希表中对应的项
                cache.erase(removed->key);//并删除哈希表中对应的项；
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {//如果 key 存在，则与 get 操作类似，
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];//先通过哈希表定位，
            node->value = value;//再将对应的节点的值更新为 value，
            moveToHead(node);//并将该节点移到双向链表的头部。
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

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

25. K 个一组翻转链表

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

• 递归
• 链表

题目

示例

代码

/**
 * 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:
    // 翻转一个子链表，并且返回新的头与尾
    pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* nex = p->next;
            p->next = prev;
            prev = p;
            p = nex;
        }
        return {tail, head};
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* hair = new ListNode(0);
        hair->next = head;
        ListNode* pre = hair;

        while (head) {
            ListNode* tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) {
                    return hair->next;
                }
            }
            ListNode* nex = tail->next;
            // 这里是 C++17 的写法，也可以写成
            // pair<ListNode*, ListNode*> result = myReverse(head, tail);
            // head = result.first;
            // tail = result.second;
            tie(head, tail) = myReverse(head, tail);
            // 把子链表重新接回原链表
            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }

        return hair->next;
    }
};