1. 链表的基础定义

1.1 主要组成

data域：用于存储每一个节点的数据
next域：用于存储指向下一个节点的指针

1.2 特点

最后指向null，意味着链表的结束。
可以无限扩容，通过指针指向其他元素可以实现空间的扩大。
存储结构特点：链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
相较于数组而言，插入，删除方便，查找不方便（需要一个一个去找）

1.3 图表写法

1.4 相关类型

近似的我们可以分为如下几种类型：

单链表
如上图，是一般的数据模型形式。
双链表
在单链表的基础上增加了一个next域，即一个节点有两个next域，一个指向前面的节点，一个指向后面的节点。这样能够一定程度上提高查找的效率。
循环链表
即最后的next指向的是head，实现了链表的循环。可以解决约瑟夫环问题。

1.5 数据结构相关操作

下面是链表有关的数据结构操作：

初始化链表结构

Struct LinkNode{
    int data;  // 定义data域内容
    ListNode *next; //指向ListNode类型元素的指针
    // 构造函数的初始化
    ListNode(int x){
        data(x);
        next(null){};
    }
}

初始化节点
ListNode* head = new ListNode(5);
删除节点

链表节点删除的主要思想有两个，第一个是寻找到要删除的位置，这个很简单实现，比对要删除的元素和指针指向的元素是否相等，如果不相等就p = p->next，移动到下个节点即可，难点是理解确定寻址指针指向的位置和删除元素的位置关系。而寻址指针指向的位置是删除元素的前一格，这个和后面具体删除的思想有关。

第二个是删除的过程操作，其中细化出来有两步，第一步是指向要删除的节点，之后直接delete带走即可，第二步是将原来指向删除节点的next域指针指向删除节点的下一个。综合这两个我们可以发现在删除节点前一个节点要做的事情是可以和其他联系起来的，他的next指向的就是删除的，而他的next我们后续也要进行操作。所以这就回应了第一个寻址思想的难点。

实现代码如下：

void DeleteElem(link L,int i)
{
link p=L,q;
int j=0;
while(p && j<i-1)
{
p = p->next;
j++;
}
if(!p||!p->next)
{cout<<"输出位置不合法"<<" ";
exit(1);
}
else{
q = p->next;
p->next = q->next;
delete q;
}
}

- 增加节点

很简单也是两步操作，第一步是定位，定位和操作和删除的差不多；第二步是增加，那么应该怎么增加呢？我们需要新引入一个指针来进行节点赋值和节点位置的操作，节点赋值很简单，就是s->data = elem，节点的位置也不难，因为插入元素，即要插入位置的原来节点得给你让出来，你要干他的事情，你的next就要指向原来节点的next即，s->next = p->next，那么你要成为他的一部分得连起来，那么原来的next就要指向你的元素，即p->next = s。注意这两步的顺序不可以搞反。

代码如下：

void AddElem(link &L, int i, int e)
{
    link p = L, s;
 int j=0;
 while(p && j<i-1)
 {
 p = p->next;
 j++;
 } //搜索插入的位置
 if(!p)
	 {cout<<"增加位置不合法"<<endl;
 exit(1);
 }
 else{
 s = new Node; //为新节点创建位置
 s->Data = e; //赋值
 s->next = p->next;
 p->next = s;
 }
}

寻找data所对应的节点
删除增加的基础，不再赘述。

2. 链表设计

2.1 复杂度

大部分是O(n)

2.2 主要思想

这里学到了一个比较重要的东西叫做虚拟头节点，他存在的意义是为了让处理头结点的时候和处理其他节点一样的自然。因为链表这种数据结构本身具有一定的局限性，其头节点无法用next指向，所以设置一个虚拟头节点，可以让头节点获得和其他节点一样的待遇。

2.3 注意点

注意什么时候需要定位到要操作节点的前一个节点，什么时候要确定的定位到那个要操作的节点。要操作节点的前一个节点主要用于添加和删除这两个操作，因为他们都需要用到前一个节点的next指针，来指向下一个节点方能对他们进行操作。而确定的定位到要操作的节点则是根据index取值的操作。
需要警惕提防节点们，因为节点们在你每次更改next域之后，他们之间的关系就进行了一次大洗牌，所以在新增和删除节点的时候一定要按步骤操作好。
有索引就有越界问题，一定看看要搜索定位的索引是否越界或者不存在。
用好while(index--)的写法，他其实和for(int i = 0; i++; i < index)是一样的，但是他的优点就是能加上一些&&，从而可以做出一些防止越界的举动。
记得在操作的时候时刻不要拿着最原始的head变量去操作，因为要返回head的时候能够帮你直接定位，而用一些替代值去进行操作就好了。

2.4 代码实现

class MyLinkedList {
public:
struct LinkNode{
    int val;
    LinkNode* next;
    LinkNode(int val): val(val), next(nullptr){}
};
    MyLinkedList() {
        size = 0; //长度
        dummyHead = new LinkNode(0); //虚拟头节点
    }
    
    int get(int index) {
        //有下标需要考虑越界问题
        if(index > size - 1 || index < 0){
            return -1;
        }
        LinkNode* cur = dummyHead -> next;
        while(index --) {
            cur = cur -> next;
        }
        return cur -> val;
    }
    
    void addAtHead(int val) {
        LinkNode* cur = new LinkNode(val);
        cur -> next = dummyHead -> next;
        dummyHead -> next = cur;
        size++;
    }
    
    void addAtTail(int val) {
        LinkNode* cur = new LinkNode(val);
        LinkNode* p = dummyHead;
        //把尾节点给找出来
        while(p -> next != nullptr){
            p = p -> next;
        }
        p -> next = cur;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        // 小于零则在头部插入节点
        if(index < 0){
            index = 0;
        }
        // 越界则无效
        if(index > size){
            return;
        }
        LinkNode* p = dummyHead;
        LinkNode* cur = new LinkNode(val);
        while(index--){
            p = p -> next;
        }
        cur -> next = p -> next;
        p -> next = cur;
        size++;
    }
    
    void deleteAtIndex(int index) {
		//判断索引是否越界
        if(index > size - 1 || index < 0){
            return;
        }
        LinkNode* cur = dummyHead;
        while(index--) {
            cur = cur -> next;
        }
        LinkNode* p = cur -> next;
        cur -> next = p -> next;
        delete p;
        size--;
    }

	ListNode* removeElements(ListNode* head, int val) {
		//虚拟头节点的建立
        ListNode* dummyHead = new ListNode();
        dummyHead->next = head;
        ListNode* cur = dummyHead;
		while(cur->next != NULL){
    		if(cur->next->val == val){
    			ListNode* tmp = cur->next;
        		cur->next = cur ->next->next;
        		delete tmp;
    }
    		else{
        		cur = cur -> next;	
    }
}
		head = dummyHead->next;
		delete dummyHead;
		return head;
    }

    private:
        LinkNode* dummyHead;
        int size;
};

3. 链表翻转

3.2 复杂度

时间复杂度：O(n)
空间复杂度：O(1)

3.3 主要思想

只要实现链表的转向即可，那么就需要有一前一后两个节点，来实现转向的操作，于是链表的转向就可以实现了。其实这里又是双指针的另一个应用场景，双指针只要涉及到需要对两个东西同时进行操作，他都能够派上用场。

3.4 注意点

我感觉这道题没有什么要注意的东西，就算要有吧，也就是要注意转移到下一个节点进行翻转的时候，定位要不能定next了，因为操作过后已经转移了，所以要在翻转前就给cur->next给标记上temp。

3.5 代码实现

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp = new ListNode(); //临时节点，用来存储要操作的下一个节点的
        ListNode* pre = NULL; //指向头节点的前一个节点
        ListNode* cur = head; //指向头节点
        while(cur){
            temp = cur->next; //标记
            cur->next = pre;  //翻转
            pre = cur; //下一组
            cur = temp; //下一组
        }
        return pre;
    }
};

4. 两两交换链表中的节点

4.1 复杂度

时间复杂度：O(n)
空间复杂度：O(1)

4.2 主要思想

要关注好移动的顺序，这道题是很好的让人们能够关注流程顺序的一道题目。

4.3 注意点

关注好移动的顺序

4.4 代码实现

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* p = new ListNode(0);
        p->next = head;
        ListNode* cur = p;
        while(cur->next != nullptr && cur->next->next != nullptr){
        ListNode* temp = cur->next; //临时节点1
        ListNode* temp1 = cur->next->next->next; //临时节点2
        cur->next = cur->next->next; //第一步操作，头节点->第二个
        cur->next->next = temp; //第二步操作，第二个->第一个
        cur->next->next->next = temp1; //第三步操作，第一个->第三个

        cur = cur->next->next;
        }
        return p->next;
    }
};

5. 删除列表的倒数第n个节点

5.1 复杂度

时间复杂度：O(n)
空间复杂度：O(1)

5.2 主要思想

还是双指针，删除这种东西好像最好双指针了，一个用来指代他的条件，另一个指针来指向要删除的值，具体而言在这道题上就是慢指针是用来指代值的，快指针的条件判断在于，倒数第几个就移动几次，终止条件本来从虚拟头节点出发到nullptr就遍历完了，那么我们删除倒数第几个就派出另一个往前先走几步就行了，那么先出发的那个到达nullptr的时候就是真正删除的那一个到达要删除的时候。

5.3 注意点

就是我们的前进的时候用while循环，其实for(int i=0; i++; i<n)和while(n--)是等价的，但是要考虑他是否越界，所以要添加上fast != null就用while好像更好一点了。

5.4 代码实现

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyList = new ListNode();
        dummyList->next = head;
        ListNode* fast = head;
        ListNode* slow = dummyList;
		//很好的判断条件，防止倒数第n个本来就是不存在的情况
        while(n-- && fast != nullptr){
            fast = fast->next;
        }
		// 一起前进
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* p = slow->next;
        slow->next = p->next;
        delete p;
        return dummyList->next;
    }
};

6. 链表相交

6.1 复杂度

时间复杂度：O(n + m)
空间复杂度：O(1)

6.2 主要思想

这道题告诉你之后难度不大，就是看看两个链表的部分是否相等就行了，怎么看呢，一个个移动，直到空为止，很容易知道应该是以最短的那个链表作为基准，因为最短的链表遍历完之后所有有可能的结果也就尘埃落定了。所以我们要做的第一步就是比对两个数组找出长度差值，之后才能够精准的进行定位。

6.3 注意点

计算完长度之后，临时指针要重定向归于原来的头节点，不然他们计算完长度之后的状态是指向nullptr的

6.4 代码实现

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cur1 = headA;
        ListNode* cur2 = headB;
        int lenA = 0, lenB = 0;
			//计算长度
        while(cur1 != NULL){
            cur1 = cur1->next;
            lenA++;
        }

        while(cur2 != NULL){
            cur2 = cur2->next;
            lenB++;
        }

        cur1 = headA;
        cur2 = headB;

        if(lenA < lenB){
            swap(lenA, lenB);
            swap(cur1, cur2);
        }

        int gap = lenA - lenB;
			//移动到同一起跑线
        while(gap--){
            cur1 = cur1->next;
        }

        while(cur1 != nullptr){
            if(cur1 == cur2){
                return cur1;
            }
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return NULL;
    }
};

7. 环形链表

7.1 复杂度

时间复杂度：O(n)
空间复杂度：O(1)

7.2 主要思想

这道题由两个部分组成，第一个部分是有没有环，第二个部分是环的入口到底在哪？首先有没有环的判断就是依据两个指针一快一慢的走，如果相遇了就能证明有环，但是这是一个必要证明，还得加上一个条件就是快指针走两步慢指针走一步，本质上就是一个追赶问题，快指针每次相对于慢指针多走了一步，那么就是链表中每一个格子都有能够遇上的机会。所以此时遇上和有环形成了一个充分必要的对应证明条件。那么入口在哪呢，假设入口离起始点的距离为x，第一次相遇两指针在距离入口y处，环的长度为y+z，那么我们可以推断出，慢指针走了x+y距离，快指针走了x+n(y+z)。那么他们相遇的话，即x+y = x+n(y+z)，我们要探究x是多少，即可以把等式变化为：x = (n-1)(y+z)+z，那么因为 y+z表示一直在绕圈可以忽略掉，所以我们可以得出一个结论叫做，起点到入环点的位置和相遇点到入环点的位置是相等的。

这里x一定没有绕环的论证在慢指针走一圈的时间快指针能走两圈，而快指针相对于慢指针每次走一步，也就是说快指针速度为2v，慢指针速度为v，快指针追上慢指针需要走的路程为y+z-a(不足一圈)，追上的时间为(y+z-a)/(2v-v),慢指针走一圈的时间为(y+z)/v，追上的时间小于慢指针走一圈的时间，所以一定能够追得上。

7.4 代码实现

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};

1. 链表的基础定义

1.1 主要组成

1.2 特点

1.3 图表写法

1.4 相关类型

1.5 数据结构相关操作

2. 链表设计

相关题目

2.1 复杂度

2.2 主要思想

2.3 注意点

2.4 代码实现

3. 链表翻转

相关题目

3.2 复杂度

3.3 主要思想

3.4 注意点

3.5 代码实现

4. 两两交换链表中的节点

相关题目

4.1 复杂度

4.2 主要思想

4.3 注意点

4.4 代码实现

5. 删除列表的倒数第n个节点

相关题目

5.1 复杂度

5.2 主要思想

5.3 注意点

5.4 代码实现

6. 链表相交

相关题目

6.1 复杂度

6.2 主要思想

6.3 注意点

6.4 代码实现

7. 环形链表

相关题目

7.1 复杂度

7.2 主要思想

7.4 代码实现