链表中的每个节点至少包括两部分：数据域与指针域
链表中的每个节点，通过指针域的值，形成一个线性结构
查找节点O(n)，插入节点O(1)，删除节点O(1)
不适合快速定位数据，适合动态的插入和删除的应用场景
和数组对应

场景一： 操作系统内的动态内存
场景二：LRU缓存淘汰算法

链表判环

image.png

    bool hasCycle(ListNode *head) {
        if (!head) return false;
        ListNode *p = head, *q = head;
        if (!q->next) return false;
        do {
            p = p->next;
            q = q->next->next;            
        } while (q && q->next && p != q);
        return p == q;
    }

找到重合的节点
算法：重合以后从头节点和重合节点一起走，第一次重合的节点就是相交节点

image.png

下面代码实现了链表全反转，起始N个反转，部分反转功能

#include <iostream>

struct LinkNode {
    LinkNode(int x) : val(x), next(nullptr) {}

    int val;
    LinkNode *next;
};

void printLink(LinkNode *p) {
    while (p) {
        printf("%d->", p->val);
        p = p->next;
    }
    printf("\n");
}

LinkNode *generateLink(int n) {
    if (!n) return nullptr;
    LinkNode *p = new LinkNode(1), *head = p;
    int m = n;
    while (--m) {
        p->next = new LinkNode(n - m + 1);
        p = p->next;
    }
    return head;
}

LinkNode *reverse(LinkNode *head) {
    if (!head || !head->next) return head;
    LinkNode *tail = head->next, *p = reverse(tail);
    head->next = tail->next;
    tail->next = head;
    return p;
}

LinkNode *reverseN(LinkNode *head, int n) {
    if (!head || !head->next || n == 1) return head;
    LinkNode *tail = head->next, *p = reverseN(tail, n - 1);
    head->next = tail->next;
    tail->next = head;
    return p;
}

LinkNode *reverseBetween(LinkNode *head, int left, int right) {
    if (left == 1) return reverseN(head, right);
    LinkNode *tail = head;
    int m = left - 1;
    while (--m) tail = tail->next;
    LinkNode *p = reverseN(tail->next, right - left + 1);
    tail->next = p;
    return head;
}

LinkNode *reverseGroup(LinkNode *head, int k) {
    int m = k;
    LinkNode *p = head;
    //初始在K的第一个，循环完p指向K的最后一个节点，或者不足K个指向空节点
    while (--m && p) p = p->next;
    //如果节点完整，调用反转函数，反转K个节点，返回q是新的head，继续下一轮重新检查和反转
    if (p) {
        p = p->next;
        LinkNode *q = reverseN(head, k);
//        printf("%d", head);
        head->next = reverseGroup(p, k);
        return q;
    } else {
        return head;
    }
}

int main() {
    printf("--Reverse all--\n");
    LinkNode *head = generateLink(6);
    printLink(head);
    LinkNode *p = reverse(head);
    printLink(p);

    printf("\n--Reverse N--\n");
    head = generateLink(6);
    printLink(head);
    p = reverseN(head, 5);
    printLink(p);
    printf("\n");

    printf("\n--Reverse Between--\n");
    head = generateLink(6);
    printLink(head);
    p = reverseBetween(head, 2, 4);
    printLink(p);

    printf("\n--Reverse Group--\n");
    head = generateLink(6);
    printLink(head);
    p = reverseGroup(head, 2);
    printLink(p);

    return 0;
}