鏈表中的每個(gè)節(jié)點(diǎn)至少包括兩部分：數(shù)據(jù)域與指針域
鏈表中的每個(gè)節(jié)點(diǎn)，通過指針域的值，形成一個(gè)線性結(jié)構(gòu)
查找節(jié)點(diǎn)O(n)，插入節(jié)點(diǎn)O(1)，刪除節(jié)點(diǎn)O(1)
不適合快速定位數(shù)據(jù)，適合動(dòng)態(tài)的插入和刪除的應(yīng)用場景
和數(shù)組對應(yīng)

場景一： 操作系統(tǒng)內(nèi)的動(dòng)態(tài)內(nèi)存
場景二：LRU緩存淘汰算法

鏈表判環(huán)

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

找到重合的節(jié)點(diǎn)
算法：重合以后從頭節(jié)點(diǎn)和重合節(jié)點(diǎn)一起走，第一次重合的節(jié)點(diǎn)就是相交節(jié)點(diǎn)

image.png

下面代碼實(shí)現(xiàn)了鏈表全反轉(zhuǎn)，起始N個(gè)反轉(zhuǎn)，部分反轉(zhuǎ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的第一個(gè)，循環(huán)完p指向K的最后一個(gè)節(jié)點(diǎn)，或者不足K個(gè)指向空節(jié)點(diǎn)
    while (--m && p) p = p->next;
    //如果節(jié)點(diǎn)完整，調(diào)用反轉(zhuǎn)函數(shù)，反轉(zhuǎn)K個(gè)節(jié)點(diǎn)，返回q是新的head，繼續(xù)下一輪重新檢查和反轉(zhuǎn)
    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;
}