线性表 || 顺序表、链表（静态、指针）

顺序表

逻辑连续物理上也连续，可静态分配（数组）也可动态分配（指针malloc，int* pInt = (int*) malloc(list_size * sizeof(int))）。

链表

物理存储位置与逻辑上的前后关系无关。可静态（指针域为数组下标），可指针（(Node*) malloc(sizeof(Node)) 或者 new Node）。

线性表算法题常见思路

顺序表

1. 计数

   • 例：主元素，求过半的众数（408真题）

   

   • 例：删除元素

     遍历时的cnt即被保留数字的新下标，别忘了长度最后要 = cnt

2. 反转，部分反转

   • 尤其要求O(1)时。。。

3. 二分

   • 例：两有序数组的中位数（408真题）

链表题

1. 反转，部分反转
2. 保留head，重新串连
3. 注意保留pre（不行就pre，curr，nxt呗，比较清楚）
4. 递归调用，栈
5. 小心NULL、小心有无头结点
6. 只动数据域（前插）
7. 头插法，尾插法，逆置法，归并法，双指针

链表原地反转的写法（空间O(1)）

1. 头结点摘下，遍历原链表，头插法
2. 三指针法（博客上看的，写起来挺不顺的= =，一直动head->next没必要）
   还需要注意，长度小于3的情况，实现见️
3. 摘下头结点，先反转后面的每个指针，最后赋head
   不需要处理特殊情况（这个好！！！），实现见️

#include <cstdio>
#include <algorithm>

using namespace std;
struct Node {
    int data = -1;
    Node *next = NULL;
};

void insertNode(Node *head, int data) {
    Node *curr = head;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    curr->next = new Node{data, NULL};
}

void reverseList1(Node *head) {
    // 判断长度：0或1 不用反转直接返回，2的话不需要三指针。
    if (!head->next || !head->next->next)
        return;
    if (!head->next->next->next) {
        Node *temp = head->next;
        temp->next->next = temp;
        head->next = temp->next;
        temp->next = NULL;
        return;
    }
    // 下面写的是3及以上的情形
    Node *p1 = head->next, *p2 = p1->next, *p3 = p2->next;
    while (p2 != NULL) {
        p2->next = head->next;
        head->next = p2;
        p1->next = p3;
//        p1 = p2; // 画个图吧 此处一错再错= =
        p2 = p3;
        if (p3) p3 = p3->next;
    }
}

void reverseList2(Node *head) {
    if (!head->next)
        return;
    Node *pre = NULL, *curr = head->next, *nxt = curr->next;
    while (curr) {
        // 经过一番调整，pre之前的指针都已经反转了，现在要将curr的next指向pre，然后接着往后走
        curr->next = pre;
        pre = curr;
        curr = nxt;
        if (nxt) nxt = nxt->next;
    }
    head->next = pre;
}

void printList(Node *list) {
    Node *curr = list->next;
    while (curr != NULL) {
        printf("%d --> ", curr->data);
        curr = curr->next;
    }
}

int main() {
    int nn;
    scanf("%d", &nn);
    Node *head = new Node;
    for (int i = 0; i < nn; i++) {
        int data;
        scanf("%d", &data);
        insertNode(head, data);
    }
    printList(head);

    reverseList1(head);
    printf("\nreverse: ");
    printList(head);

    reverseList2(head);
    printf("\nreverse: ");
    printList(head);
    return 0;
}

回顾：408真题-链表重排

只会写PAT的假链表，真链表指针一多就蒙了。

2019 408真题

虽然PAT上那题挺顺利就AC了，但是并不会用真链表搞空间O(1)的写法= =
解析：

1. 先找到链表中点
   两个指针。p1步长为1，p2步长为2。p2走到尾的时候，p1刚好在中点。
2. 反转链表的后半部分
   反转的代码见️。（reverse()用多了的废人如我。。。
3. 两个指针分别初始为头、中点，串起来。