// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
//也可以不定义构造函数，使用默认构造函数，但是这个构造函数不会初始化任何成员变量

//自己定义的构造函数
ListNode* head = new ListNode(5);

//默认构造函数
ListNode* head = new ListNode();
head->val = 5;

操作

1.删除结点

将B的next指向D就可以了

在C++中手动释放掉C结点，delete就行?

2.添加结点

B的next指向M，M的next指向C

性能分析

	插入、删除	查询	使用场景
数组	O(n)	O(1)	数据固定，频繁查询，较少增删
链表	O(1)	O(n)	数据不固定，频繁增删，较少查询

经典方法

虚拟头结点

思路

设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除

例题：力扣203

给你一个链表的头节点?head?和一个整数?val?，请你删除链表中所有满足?Node.val == val?的节点，并返回?新的头节点?。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode*dummyhead=new ListNode(0);
        dummyhead->next=head; //虚拟头节点指向head结点
        ListNode*cur=dummyhead; //当前结点是dummyhead
        while(cur->next!=NULL){ //如果下一位不是空--没有到末尾 还在循环中判断
            if(cur->next->val==val){
                ListNode*temp=cur->next; //定义临时变量 方便回收节点
                cur->next=cur->next->next; //当前节点的next指向删除节点的下一位
                delete temp; //手动回首内存空间
            }
            else{
                cur=cur->next; //指向下一位
            }
        }
        head=dummyhead->next;//头节点是dummyhead的下一个
        delete dummyhead;//回收节点
        return head;//返回头节点
    }
};

链表的基本操作

思路

对链表进行增删改查的基本操作

例题：力扣707

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val?和?next。val?是当前节点的值，next?是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性?prev?以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第?index?个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为?val?的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为?val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第?index?个节点之前添加值为?val??的节点。如果?index?等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引?index 有效，则删除链表中的第?index 个节点。

class MyLinkedList {

public:
    //定义链表结构体
    struct LinkedNode{
        int val;
        LinkedNode*next;
        LinkedNode(int val):val(val),next(nullptr){}
    };
    //初始化链表
    MyLinkedList() {
        dummyhead = new LinkedNode(0);//这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        size=0;//链表大小置为0
    }
    
    int get(int index) {
        LinkedNode*cur=dummyhead->next;//一个辅助变量 指向dummyhead的下一位
        if(index<0||index>size-1){
            return -1;//非法返回-1
        }
        //合法操作
        while(index--){
            cur=cur->next;
        }
        return cur->val;//返回cur的值
    }
    //在头位置添加
    void addAtHead(int val) {
        LinkedNode*newhead=new LinkedNode(val);
        newhead->next=dummyhead->next;//插入的结点为头节点
        dummyhead->next=newhead;
        size++;//数量要增加
    }
   //在尾巴插入 
    void addAtTail(int val) {
        LinkedNode*newtail=new LinkedNode(val);
        LinkedNode*cur=dummyhead;//辅助变量
        while(cur->next!=nullptr){
            cur=cur->next;
        }
        cur->next=newtail;
        size++;//数量要增加
    }
    //按照序列插入
    void addAtIndex(int index, int val) {
        if(index>size||index<0)
            return;
        LinkedNode*indexnode=new LinkedNode(val);
        LinkedNode*cur=dummyhead;
        while(index--){
            cur=cur->next;
        }
        indexnode->next=cur->next;
        cur->next=indexnode;
        size++;//数量增加
    }
    //删除结点
    void deleteAtIndex(int index) { //想不通cur是指向dummyhead还是指向dummyhead->next的时候 带入0试一下
        if (index >= size || index < 0) {
            return;
        }
        LinkedNode* cur = dummyhead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;
    }
    //打印链表
    void printLinkedlist(){
        LinkedNode*cur=dummyhead;
        while(cur->next!=nullptr){
            cout<<cur->next->val<<" ";
            cur=cur->next;
        }
        cout<<endl;
    }
    private:
    int size;
    LinkedNode*dummyhead;
};

反转链表

思路

1.如果定义一个新的链表，实现链表元素的反转，是对内存空间的浪费

2.只需要改变链表的next指针的指向，直接将链表反转，不用重新定义一个新的链表

①首先定义一个cur指针，指向头结点，定义pre指针，初始化为null

②temp保存cur->next结点，改变cur->next的指向为pre，继续移动cur和pre

?③cur指针指向null，循环结束，链表反转完毕，返回return pre即可，pre指向了新的头结点。

例题：力扣206

给你单链表的头节点?head?，请你反转链表，并返回反转后的链表。

//如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
//只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表
class Solution {
public:
    //递归法
    ListNode* reverse(ListNode*cur,ListNode*pre){
        if(cur==NULL) return pre;
        ListNode*temp=cur->next;
        cur->next=pre;
        return reverse(temp,cur);
    }
    ListNode* reverseList(ListNode* head) {
        //双指针写法
       /* ListNode*pre=NULL;//头的前一位 也是cur->next新的指向位置
        ListNode*cur=head;//从头开始
        ListNode*temp;//临时遍历 保存cur->next的值 防止丢失
        while(cur){
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;*/
        return reverse(head,NULL);
    }
};

删除倒数第N个结点

思路：

双指针的经典应用——如果要删除倒数第n个结点，让fast移动n步，然后让fast和slow同时移动，知道fast指向链表末尾。删掉slow所指向的结点就可以了。

①设置虚拟头结点dummyhead

②定义fast和slow指针，初始值为虚拟头结点

③fast首先走n+1步，slow和fast同时移动，直到fast指向末尾。

④删除slow所指向的下一个结点

例题：力扣19

给你一个链表，删除链表的倒数第?n?个结点，并且返回链表的头结点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode*dummyhead=new ListNode(0);
        ListNode*fast;
        ListNode*slow;
        dummyhead->next=head;
        fast=dummyhead;
        slow=dummyhead;
        //让fast指针走n+1步 找到快指针的位置
        n=n+1;
        while(n--&&fast!=NULL){
            fast=fast->next;//挪动指针
        }
        //让slow和fast同时出发，快指针指向null，慢指针所指的位置就是倒数第n个结点
        while(fast!=NULL){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;//执行删除操作

        return dummyhead->next; //返回头结点了
    }
};

链表相交

思路：

求两个链表交点节点的指针。**交点不是元素数值相等，而是指针相等

①curA指向链表A的头结点，curB指向链表B的头结点

②分别求出两个链表的长度，求出两个链表长度的差值，curA移动到和curB末尾对齐的位置

③比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA==curB，则找到交点；否则循环退出返回空指针。

例题：力扣面试题 02.07

给你两个单链表的头节点?headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode*curA=headA;
        ListNode*curB=headB;
        int lenA=0;
        int lenB=0;
        //分别求A和B的长度
        while(curA!=NULL){
            lenA++; //A的长度
            curA=curA->next;
        }
        while(curB!=NULL){
            lenB++; //B的长度
            curB=curB->next;
        }
        //让他们分别为表头，这样才能从头开始移动
        curA=headA;
        curB=headB;
         // 让curA为最长链表的头，lenA为其长度
        if(lenB>lenA){
            swap(lenA,lenB);
            swap(curA,curB);
        }
        //挪动A链表的curA
        int gapp=lenA-lenB;
        while(gapp--&&curA!=NULL){
            curA=curA->next;
        }
        //遍历curA 和 curB，遇到相同则直接返回
        while(curA!=NULL){
            if(curA==curB){
                return curA;
            }
            curA=curA->next;
            curB=curB->next;
        }
        return NULL;

    }
};

环形链表

思路：

1.判断链表是否有环：快慢指针法

分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。

2.如果有环，如何找到环的入口

假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。

①从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。

②在相遇节点处，定义一个指针index1，在头结点处定一个指针index2

③让index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。

例题：力扣142

给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode*fast=head;//从头开始走
        ListNode*slow=head;//从头开始
        //先走index1，让index1找到
        while(fast!=NULL&&fast->next!=NULL){
            fast=fast->next->next; //快指针走2步
            slow=slow->next;//慢指针走1步
            //--找环
            if(slow==fast){//快&慢指针相遇了
                ListNode*index1=fast;//index1指向快慢指针相遇的位置，从相遇位置开始出发
                ListNode*index2=head;//index2指向头位置，从头开始出发
                //--找环的入口
                while(index1!=index2){//还没碰见呢--循环
                    index1=index1->next;//移动
                    index2=index2->next;
                }
                return index1;//返回刚碰见
            }
        }
        return NULL;//没有环 返回空
    }
};

链表是数据结构中我最不熟练认为最难的一部分。。。这次从头到尾捋了一遍，感觉更清晰了，但是还需要再练习一遍。。