链表

这个在leetcode上刷的链表形式，可以分离到leetcode那边

LeetCode上的链表

这种专门考动态链表本身的操作基本上只出现在工作面试和leetcode比赛中，一般在其它比赛中不太常见。

链表定义

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

主要要熟练掌握链表的递归和迭代操作。

反转链表

反转链表I

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        
        while (cur != NULL) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};

反转链表II

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy_head = new ListNode(-1, head);
        ListNode* p = dummy_head;

        int i = 1;
        while (i < left) {
            p = p->next;
            i ++;
        }

        ListNode* pre = p;
        ListNode* cur = p->next;
        while (left <= i && i <= right) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
            i ++;
        }
        
        p->next->next = cur;
        p->next = pre;

        return dummy_head->next;
    }
};

邻接表主要应用于

1. 树与图的存储
2. hash表的拉链法存储

单链表

双向链表

很牛逼

[https://www.acwing.com/activity/content/code/content/5818478/]