目录
1.单链表的结构
2.单链表的创建
1.头插法
2.尾插法
3.单链表的遍历
4.节点的删除
1.删除指定大小的节点（删除第一个）
2.删除所有值为key的节点
3.删除链表中的重复项
4.删除链表中的重复元素2
5.删除倒数第K个元素
5.链表的反转
1.反转链表1
2.反转链表2
6.链表是否有环
7.合并两个有序链表
链表在C++中是一种非常重要的数据结构，今天我们就来对单链表进行实现。
1.单链表的结构
单链表的结构是由多个节点构成，其中节点的结构如下：
给出它结构体的代码：
struct Node {int val;//信息域Node* next;//指针域Node(int value) : val(value), next(nullptr) {}
};包含一个信息域和指针域，其中指针域用来存放当前节点的值，而指针域则是指向下一个节点的位置。多个节点就构成了一个单链表，其中，最后一个节点指向nullptr。
2.单链表的创建
单链表的创建有两种方法：头插法和尾插法
1.头插法
顾名思义，就是把当前节点放到最前面。
假设插入的节点为p，先让p节点指向头节点的下一个节点，然后头结点的下一个节点指向p节点，这样就把p节点插入进来了。（在创建第一个节点时，此时head指向的为空，p为尾部的节点，也应该指向nullptr，所以指向head的next是没有问题的）。然后让head的值等于数组最后一个元素的值，这样链表就创建好了。
创建的代码如下：
void createListNode1(Node* head, vector<int>& v) {int n = v.size();Node* p;for (int i = 0; i < n-1; i++) {p = new Node(v[i]);p->next = head->next;//构建新结点和原来头结点后面结点的连接head->next = p;//构建头结点和新结点的连接}head->val = v[n - 1];//头节点的值为最后一个元素的值
}2.尾插法
尾插法就是把元素查到链表的尾部
假设插入的节点为p，这里用一个节点p指向这个链表的尾部。让s的next指向p节点，然后更新s即可。
void createListNode2(Node* head, vector<int>& v) {int n = v.size();Node* p;head->val = v[0];Node* s = head;for (int i = 1; i < n; i++) {p = new Node(v[i]);s->next = p;s = p;}
}3.单链表的遍历
这个比较简单，这里直接给出代码
void printListNode(Node* head) {Node* p = head;while (p) {cout << p->val << " ";p = p->next;}
}4.节点的删除
思路：想要删除一个节点，那么必须让它前面的节点指向它后面的节点，那么这个节点就被删除了。
例如，若想要删除节点p，那么只需要找到它的前驱节点（这里是s），让前驱节点指向p的下一个节点即可。
如果想要删除的元素为第一个元素，情况就有所不同，因为第一个节点没有前驱节点，此时，我们就需要构建一个虚头结点，让这个节点指向头节点，那么删除头节点的操作就和上面一样了。
下面来看一些常见的删除节点的题，主要是以力扣上面的为主，因为力扣上面会主动删掉没用的节点，所以后序代码中没写delete 节点。
1.删除指定大小的节点（删除第一个）
Node* DeleteNode(Node* head, int key) {//先构建一个虚头节点，让删除头节点的操作和其他节点一样Node* HEAD = new Node;HEAD->next = head;Node* cur=head;Node* pre = HEAD;while (cur->val != key) {cur = cur->next;pre = pre->next;}pre->next = cur->next;return HEAD->next;
}2.删除所有值为key的节点
思路：在上一问的基础上，遍历所有的元素，如果等于key就删除，同时要将cur=pren->ext，否则就往后面走。
Node* DeleteNode(Node* head, int key) {//先构建一个虚头节点，让删除头节点的操作和其他节点一样Node* HEAD = new Node;HEAD->next = head;Node* cur = head;Node* pre = HEAD;while (cur) {if (cur->val == key) {pre->next = cur->next;cur = pre->next;}else {cur = cur->next;pre = pre->next;}} return HEAD->next;
}3.删除链表中的重复项
给定一个升序的链表，要求删除链表中的重复元素，使每个元素仅出现一次，返回头结点
对应力扣：83. 删除排序链表中的重复元素 - 力扣（LeetCode）
思路：这里跟之前的删除元素不太一样，因为第一个节点不会被删除，所以就不需要构建虚头节点。还是双指针，一个指向头节点的下一个节点，一个指向头结点，然后while遍历，如果当前两个指针指向的元素的大小相同，就删除后面那个元素，如果不相同两个指针就往后面移动一位。
ListNode* deleteDuplicates(ListNode* head)
{if (head == nullptr || head->next == nullptr)return head;ListNode* fast = head->next;ListNode* slow = head;while (fast) {if (fast->val == slow->val) {slow->next = fast->next;fast = slow->next;}else {fast = fast->next;slow = slow->next;}}return head;
}4.删除链表中的重复元素2
在上一题的基础上，新增了一个条件，如果这个元素重复了就给他删除。
思路：因为可能删除第一个节点，所以要建立一个虚头节点HEAD，让指针fast指向HEAD,然后遍历，遍历的条件为fast的下一个节点和下个节点的下个节点都存在。如果说两个指向的值都相同，那么说明存在重复元素，先用一个变量存这个值，然后挨个往后面查，如果这个元素的值和这个变量相等就删除这个元素。否则，fast就往后移动一位。
对应力扣：82. 删除排序链表中的重复元素 II - 力扣（LeetCode）
ListNode* deleteDuplicates(ListNode* head) {if (head == nullptr || head->next == nullptr)return head;ListNode* HEAD = new ListNode(0);HEAD->next = head;ListNode* fast = HEAD;while (fast->next && fast->next->next) {if (fast->next->val == fast->next->next->val) {int x = fast->next->val;while (fast->next && fast->next->val == x) {fast->next = fast->next->next;}} else {fast = fast->next;}}return HEAD->next;}5.删除倒数第K个元素
思路：快慢指针，先让快指针走n步，然后快慢指针一起走，当走到快指针为空时，此时慢指针所指向的下一个节点就是要删除的结点。先建立一个虚头节点，快指针指向head节点，慢指针指向虚头节点。
对应力扣：LCR 021. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* HEAD= new ListNode(0);HEAD->next=head;ListNode* fast=head;ListNode* slow=HEAD;while(n--){fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}slow->next=slow->next->next;return HEAD->next;}5.链表的反转
1.反转链表1
链表反转是一个非常经典的问题。
思路：如上图，初始化两个指针，一个指向头结点，一个指向nullptr。翻转的过程如下：先将cur的next存起来，因为等会要用，然后让cur指向pre。此时cur变成了下一个要拼接的结果，所以cur和pre都要向后移动开始翻转下一个节点，pre直接等于cur即可，而cur则直接变成刚刚存起来的那个节点。代码如下：
对应力扣：206. 反转链表 - 力扣（LeetCode）
ListNode* reverseList(ListNode* head) {ListNode* cur=head;ListNode* pre=nullptr;while(cur){ListNode* p=cur->next;cur->next=pre;pre=cur;cur=p;}return pre;}2.反转链表2
思路：先找到要翻转的链表的头节点和尾节点，然后调用函数对它进行反转，返回值是一个键值对，分别为返回后的头节点和尾节点。然后再和原来的连接起来即可。
对应力扣：92. 反转链表 II - 力扣（LeetCode）
pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode* tail) {ListNode* pre = nullptr;ListNode* cur = head;while (pre != tail) {ListNode* p = cur->next;cur->next = pre;pre = cur;cur = p;}return {tail, head};}ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* HEAD = new ListNode(0);HEAD->next = head;ListNode* pre = HEAD;//要翻转的链表的头节点的上一个节点，便于后序连接ListNode* l = head;ListNode* r = head;left--;right--;while (left--) {pre = pre->next;l = l->next;}while (right--) {r = r->next;}ListNode* tail = r->next;//要翻转的链表的尾节点的后一个节点，便于后序连接pair<ListNode*, ListNode*> ans = reverseList(l, r);l = ans.first;r = ans.second;pre->next = l;r->next = tail;return HEAD->next;}6.链表是否有环
思路：快慢指针，让一个指针走的快，一个指针走的慢，如果存在一个环，则一定会有这两个点相遇，如果发现某个指针为nullptr，则无环。
对应力扣：141. 环形链表 - 力扣（LeetCode）
bool hasCycle(ListNode* head) {//快慢指针，让一个指针走的快，一个指针走的慢，如果存在一个环，则一定会有这两个点相遇，如果发现某个指针为nullptr，则无环if(head==nullptr || head->next==nullptr) return false;ListNode* slow = head;ListNode* fast = head->next;while (slow != fast) {if (fast&& fast->next) {fast = fast->next->next;slow = slow->next;}elsereturn false;}return true;}7.合并两个有序链表
思路：建立两个节点，一个头节点和一个尾节点。先处理头节点，如果头节点为空，那么它就等于list1和list2中那个较小的。如果不为空，p就为两者中较小的，同时更新p，保证p是已经拼接好的的链表的最后一个节点，还要更新list1和list2两个指针。
对应力扣：21. 合并两个有序链表 - 力扣（LeetCode）
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == nullptr)return list2;if (list2 == nullptr)return list1;ListNode* head = nullptr;ListNode* p;while (list1 && list2) {if (head == nullptr) {head = list1->val <= list2->val ? list1 : list2;p = head;} else {p->next = list1->val <= list2->val ? list1 : list2;p = p->next;}if (list1->val <= list2->val)list1 = list1->next;elselist2 = list2->next;}if (list1 == nullptr)p->next = list2;elsep->next = list1;return head;}总结：在做链表相关的题时，一定要记得画图，不然写着写着就容易迷糊了。