前言

初识LeetCode与算法，将在此系列文章里面，记录自己的算法学习经历，前期主要是监督自己学习打卡，后期我会将自己对知识的理解，慢慢补充到文章当中，希望大家能在阅读我的文章中，有所收获。该系列文章的刷题顺序以代码随想录为线索。

一、移除链表元素

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

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、直接删除，不添加虚拟头结点，此时，删除头结点的方法和其他节点不同
2、添加虚拟头结点，此时，删除头结点方法和其他节点相同

代码：

# 直接删除法class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 删除头结点while(head != NULL && head->val == val){ListNode* tmp = head->next;head = head->next;delete tmp;}// 删除非头结点ListNode* cur = head;while(cur != NULL && cur->next != NULL){if(cur->next->val == val){ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;}else{cur = cur->next;}}return head;}
};#设置虚拟头结点法
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0);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;}
};

二、设计链表

题目：
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

提示：

所有val值都在 [1, 1000] 之内。
操作次数将在  [1, 1000] 之内。
请不要使用内置的 LinkedList 库。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、添加虚拟节点

代码：

class MyLinkedList {
public:struct LinkedNode{int val;LinkedNode* next;LinkedNode(int val): val(val),next(nullptr){}};MyLinkedList() {_dummyHead = new LinkedNode(0);_size = 0;}int get(int index) {if(index > (_size - 1)|| index < 0){return -1;}LinkedNode* cur = _dummyHead->next;while(index--){cur = cur->next;}return cur->val;}void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(cur->next != nullptr){cur = cur->next;}cur->next = newNode;_size++;}void addAtIndex(int index, int val) {if (index > _size) {return;}LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(index--){cur = cur->next;}newNode->next =cur->next;cur->next = newNode;_size++;}void deleteAtIndex(int index) {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--;}private:int _size;LinkedNode* _dummyHead;
};

三、反转链表

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、将指针进行反转，这样就可以实现链表的反转

代码：

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

四、两两交换链表中的节点

题目：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、直接将图画在草稿纸上，避免出错！

代码：

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;while(cur->next != nullptr && cur->next->next != nullptr){ListNode* tmp = cur->next;ListNode* tmp1 = cur->next->next->next;cur->next = cur->next->next;cur->next->next = tmp;cur->next->next->next = tmp1;cur = cur->next->next;}return dummyHead->next;}
};

五、删除链表的倒数第N个节点

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、双指针法，一个fast指针和一个slow指针，让fast指针先往前走n+1步，多一步的话，可以使slow指针指向删除节点的前面节点，方便删除操作。

代码：

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n-- && fast != NULL){fast = fast->next;}fast = fast->next;while(fast != NULL){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummyHead->next;}
};

六、链表相交

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

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
1、用两个指针分别指向两个链表的表头，先求出两个链表的长度，再求出两个链表的差值。将长链表的表头移动到和短链表的表头平齐。之后比较两个指针的值是否相同，如果相同则放回；如果不相同则指针分别偏移一个单位。

代码：

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;int lenA = 0,lenB = 0;while(curA != NULL){lenA++;curA = curA->next;}while(curB != NULL){lenB++;curB = curB->next;}curA = headA;curB = headB;if(lenB > lenA){swap(lenA,lenB);swap(curA,curB);}int gap = lenA - lenB;while(gap--){curA = curA->next;}while(curA != NULL){if(curA == curB){return curA;}curA = curA->next;curB = curB->next;}return NULL;}
};

七、环形链表 II

题目：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search

思路：
也是双指针法，一个快指针和一个慢指针，当两个指针相遇的时候；在定义两个指针，一个指针从相遇点开始走，另一个指针从头结点开始走，当两个指针相遇的时候，就是入口结点。
（具体推理过程，参看代码随想录）

代码：

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* slow = head;ListNode* fast = head;while(fast !=NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if(slow == fast){ListNode* index1 = fast;ListNode* index2 = head;while(index1 != index2){index1 = index1->next;index2 = index2->next;}return index2;}}return NULL;}
};