数据结构第2章 - 线性表(Part 2)

写在开头

由于前面顺序表中的MAX_SIZE并非真正的无限空间而将使最大存储空间受到局限、对于少量数据来说又会浪费很多的内存，插入、删除元素过于缓慢，我们寻求一种更加高效且合理的存储结构——链表。链表由于其使用指针并且动态开辟新的内存区域的方式而成为更受欢迎、使用更广泛的一种线性表存储结构。

线性表存储结构2 - 链表

链表1 - 单链表

单链表的定义

单链表是用一组任意的存储单元存放线性表的元素，通过每个节点存储它下一个数据所在内存地址的指针而存放整张线性表。

定义代码：

template<class DataType>
class NodeList {
    public:
    	DataType val; //存储该节点的值
    	NodeList* next; //存储下一个节点的地址
    	NodeList(DataType v) : val(v), next(nullptr) {}
    	NodeList(DataType v, NodeList* n) : val(v), next(n) {}
};

是不是非常有趣？这边的存储不再使用像顺序表里面那种开一大堆地方的策略，是用多少开多少，通过我们所熟悉的指针（熟悉吗？）将所有数据块穿起来，一个节点连着一个节点，非常灵活。

不只是在存储上链表展现出其灵活的存储特性，在其增删改查的操作中，链表同样能够实现极优于顺序表的执行效率。

单链表的增删改查

这边直接给出力扣上对于链表的设计代码（轻微修改和注释），关于详细实现直接进传送门就好了，这边的数据由于是int，因此链表也只保存int类型的数据。

传送门：设计链表 - 设计链表 - 力扣（LeetCode） (leetcode-cn.com)

class MyLinkedList {
public:
    struct LinkedNode { //链表节点结构体
        int val; //值
        LinkedNode* next; //下一个节点地址
        LinkedNode(int val):val(val), next(nullptr){} //带参数创建链表节点
    };

    MyLinkedList() { //构造新链表类
        _dummyHead = new LinkedNode(0);//dummyHead作用只是指向链表开头
        _size = 0;//为了核验插入位置和方便对链表进行操作，设置size位
    }

    int get(int index) { //获取第index个节点的数据
        if (index > (_size - 1) || index < 0) { //范围检测和异常提醒
            throw "index out of bounds";
        }
        LinkedNode* cur = _dummyHead->next; //从真正的第一个数据节点开始向后遍历
        while(index--){
            cur = cur->next; //向后移动指针
        }
        return cur->val; //返回所需值
    }

    void addAtHead(int val) { //在开头插入节点
        LinkedNode* newNode = new LinkedNode(val); //由于dummy的存在，开头添加变得简单很多
        //这边的new就相当于LinkedNode* newNode =(LinkedNode*)malloc(sizeof(LinkedNode))
        //此注释给一些不太看得懂C++的人;P
        newNode->next = _dummyHead->next; //先让新的头节点连上后面的内容再进行操作
        _dummyHead->next = newNode; //指向新的头节点，想想如果不进行上一步会发生什么
        _size++; //大小+1
    }

    void addAtTail(int val) { //在尾部插入节点
        LinkedNode* newNode = new LinkedNode(val); //创建新节点
        LinkedNode* cur = _dummyHead; //记录头节点，因dummy指针向后移动后会丢失原来的地址，这边不直接操作dummy
        while(cur->next != nullptr){ //保证没到最后一个节点
            cur = cur->next; //向后移
        }
        cur->next = newNode; //将最后一个节点的next指向要添加的节点
        _size++; //大小+1
    }

    void addAtIndex(int index, int val) { //任意指定位置插入
        if (index > _size) { //范围检测
            throw "index overflow";
        }
        LinkedNode* newNode = new LinkedNode(val); //要插入的节点
        LinkedNode* cur = _dummyHead; //同上，不直接操作头地址指针
        while(index--) { //后移
            cur = cur->next;
        }
        newNode->next = cur->next; //新节点next指向上一个节点的下一个节点，理解一下
        cur->next = newNode; //更新next
        _size++; //大小+1
    }

    void deleteAtIndex(int index) { //删除任意指定节点
        if (index >= _size || index < 0) { //范围检测
            throw "index out of bounds";
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next; //将tmp指向要删除节点
        cur->next = cur->next->next; //将tmp上一个节点next指向tmp的下一个节点
        delete tmp; //将tmp从内存中删除
        _size--; //大小-1
    }
private:
    int _size; //链表大小
    LinkedNode* _dummyHead; //链表头
};

知识点：单链表中的环

由于next是直接存储链表的地址，设想一下，如果一个链表节点的next再次指向它前面的某个节点会怎么样？环就出现啦。

这么好玩的东西我们肯定要找出来啦~ 该怎么找呢？

1.快慢指针：判环

想一下下面的场景：两个人跑步，一个快一个慢，那么在环形的操场上，跑得快的肯定能在跑完一圈之后追上那个跑的慢的同学；反过来说，如果这个跑得快的能够和跑的慢的相遇，那么说明他们在一个环里面~

抽象一下，快慢两个指针，如果快指针走到头了，那么就没有环，但当它和慢指针相遇了，那么就说明到环里了

这个只要给出代码，就不难理解：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr)return false;
        ListNode *fast=head->next;
        ListNode *slow=head;
        while(fast!=slow){
            if(fast==nullptr||fast->next==nullptr)return false;
            fast=fast->next->next;
            slow=slow->next;
        }
        return true;
    }
};

2.快慢指针：寻找入口

发现了环，怎么找到环的入口呢？由于快指针比慢指针多走了一圈，那么此时将慢指针向前一步，快指针从头重新以和慢指针一样的速度向后，就能在环的入口相遇啦

证明：传送门：环形链表Ⅱ

代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==nullptr)return nullptr;
        ListNode *fast=head->next;
        ListNode *slow=head;
        while(fast!=slow){
            if(fast==nullptr||fast->next==nullptr)return nullptr;
            fast=fast->next->next;
            slow=slow->next;
        }
        fast=head;
        slow=slow->next;
        while(slow!=fast){
            slow=slow->next;
            fast=fast->next;
        }
        return fast;
    }
};

知识点：反转链表

有时候我们需要将一个链表头尾反转，该怎么做呢？由于我们现在讲的还是单链表，这边给出我非常喜欢的一种反转方法，想想链表的操作，相信多看几遍就会啦：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        while(head!=nullptr){
            ListNode* node=head->next;
            head->next=dummy->next;
            dummy->next=head;
            head=node;
        }
        return dummy->next;
    }
};