学会链表了还不赶紧刷题（力扣刷题笔记）
个人主页：欢迎大家光临——>沙漠下的胡杨
各位大帅哥，大漂亮
如果觉得文章对自己有帮助
可以一键三连支持博主
你的每一分关心都是我坚持的动力
☄： 本期重点：链表的力扣刷题笔记
希望大家每天都心情愉悦的学习工作。
目录
1. 移除链表题目分析：
代码实现：
思路1：
思路2：
2. 反转链表题目理解：
代码实现：
思路1：
思路2：
3. 链表中间结点题目分析：
代码思想实现：
4. 链表倒数第k个结点题目分析：
代码实现：
5. 合并链表题目分析：
代码实现：
6.分割链表题目分析：
代码实现：
我们链表的章节已经结束啦，我们学会了多少呢？来刷题验证下吧！
203. 移除链表元素
1. 移除链表题目分析：
简单来说就是遍历链表然后删除其中值为 val 的节点，最后返回链表的头即可。
思路1：
我们可以创建一个新的链表，然后遍历原链表，把值不等于 val 的节点拿下来尾插，最后返回我们创建的链表。
思路2：
我们可以再原链表的基础上进行直接删除值为 val 的节点，然后返回原来的头就好啦。
在上面的思路下，我们可以使用头结点，也可以不使用头结点，实现方式随意，下面就简单实现。
代码实现：
思路1：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur = head; struct ListNode* Newhead = NULL; Newhead = head = (struct ListNode*)malloc(sizeof(struct ListNode)); Newhead->next = NULL; while(cur) { if(cur->val != val) { Newhead->next = cur; Newhead = Newhead->next; } cur = cur->next; } Newhead->next = NULL; struct ListNode* tmp = head->next; free(head); return tmp;}1. 我们先创建一个 cur 遍历指针
2. 然后我们开辟一个链表，把head 和我们开辟的Newhead都赋值为开辟的链表，把开辟的链表的 next 置为NULL
3. 然后我们进行遍历，如果遇到节点的值不等于 val 那么我们就把节点拿下来尾插，更新Newhead，让 cur 向后走，如果节点的值等于 val ，那么我们直接跳过。
4 .我们要把Newhead的next置空，否则会有访问NULL问题。
5. 再用指针值保存要返回的结点，把开辟的空间free掉就好啦。
需要注意的是步骤 4 和 5 ，很容易忘记置NULL和 形成内存泄漏。
思路2：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur = head; struct ListNode* prev = NULL; while(cur) { if(cur->val == val) { if(cur == head) { head = cur->next; free(cur); cur = head; } else { prev->next = cur->next; free(cur); cur = prev->next; } } else { prev = cur; cur = cur->next; } } return head;}1. 我们创建一个指针 cur 和 prev，cur为了遍历，prev是为了删除结点后链接剩下的结点。
2. 遍历链表，分为2种情况，分别是头部需要删除，其他部位删除。
3.头部删除时，先用head 保存 cur的下一个结点，free掉cur指针，把cur赋值为head。
4. 其他部位删除，此时的prev不为NULL了，我们使用 prev->next 保存 cur->next，然后free掉 cur 结点，然后把cur赋值为prev->next。
5.如果cur->val 不等于 val 时，我们直接把 cur赋值给 prev，然后让cur向后就好了。
注意：我们要删除时，要考虑头部的删除，并且我们还要注意不要出现访问NULL的问题。
206. 反转链表
2. 反转链表题目理解：
这个要看的话比较简单，只需要把链表指向反着来就好了。
思路1：
我们可以在原链表的基础上改变链表的指向就好了。
思路2：
我们可以把链表每个结点拿下来头插，然后把第一个节点置NULL。
代码实现：
思路1：
struct ListNode* reverseList(struct ListNode* head){ if(head == NULL) { return NULL; } struct ListNode* n1 = NULL; struct ListNode* n2 = head; struct ListNode* n3 = n2->next; while(n2) { n2->next = n1; n1 = n2; n2 = n3; if(n3) { n3 = n3->next; } } return n1;}1. 我们创建3个指针，分别是n1 n2 n3，n1为空，n2为head，n3为n2->next，这样使三个指针相邻，我们可以方便迭代和转指向。
2. 接着我们就直接用 n2 遍历链表，转指向就是把 n2->next 指向n1。
3. 迭代，就是把n2 给 n1，n3 给 n2，n3等于n3->next，如果n3为空，那么n3就不动，移动剩下的n1 和 n2，一直到n2为NULL时，就结束。
4. 我们最后返回的是n1。
注意：我们考虑下极端情况，当链表为NULL时，我们操作就会访问NULL，所以链表为空时我们直接返回。
思路2：
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* Newnode = NULL; struct ListNode* cur = head; while(cur) { struct ListNode *tmp = cur->next; cur->next = Newnode; Newnode = cur; cur = tmp; } return Newnode;}1. 我们创建两个指针，cur 为了遍历，Newnode为了插入。
2. 遍历链表，再创建一个结点保存cur的下一个结点。
3. 然后链接，把cur->next 赋值为 Newnode，把Newnode 赋值为 cur，最后把cur向后走。
4.最后返回Newnode就好了。
注意：我们第一次cur->next就把第一个节点赋值为NULL了，就不用做特殊处理了。剩下的就是一个个结点的链接。
876. 链表的中间结点
3. 链表中间结点题目分析：
这道题就是用一个思想，就是快慢指针的思想，必须要往快慢指针想才可以解出来。
快指针一次走两步，慢指针一次走一步，这样当快指针走到链表结尾时，慢指针的位置刚好是中间的结点，这道题重点不是代码了，而是实现的思路，以及为什么必须要一个指针走两步，一个指针走一步，其他方式实现不行吗？
代码思想实现：
struct ListNode* middleNode(struct ListNode* head){ struct ListNode* fast = head; struct ListNode* slow = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow;}定义快慢指针，然后让它们向后走，一直到快指针为空，或者快指针的 next 为空了停止，然后返回慢指针。
注意：我们写终止条件时，我们判断终止的条件是 快指针为空，或者快指针的 next 为空，但是我们写的是继续的条件，我们想的都是终止条件，写出来的都是继续条件，这点逻辑相反，需要注意。
为什么这样刚好能返回中间结点：
首先，一个指针走两步，一个指针走一步，当快的指针走完链表时，慢指针刚好才走到一半的位置，如果快指针走其他步数时，我们不能够追上，因为其他步数时，要么是快指针走完了链表，结果慢指针还走到一半，要么是快指针走完了，慢指针走过了中间结点，不能保证没次刚好都在中间结点。
剑指 Offer 22. 链表中倒数第k个节点
4. 链表倒数第k个结点题目分析：
这道题我们还是用快慢指针的思路来求解，首先我们可以让快指针先走 k-1 步，然后在让快慢指针一起走，当快指针的next为空时，返回慢指针就是倒数第k个节点。
代码实现：
struct ListNode* getKthFromEnd(struct ListNode* head, int k){ struct ListNode* slow = NULL; struct ListNode* fast = NULL; slow = fast = head; while(--k) { if(fast->next == NULL) { return NULL; } fast = fast->next; } while(fast->next) { slow = slow->next; fast = fast->next; } return slow;}1.首先我们创建快慢指针，然后先让快指针先走 k-1 步，循环条件为 --k，因为k-- 就是k次循环，而 --k 就是 k-1 次循环吗，我们要走 k-1 步，所以使用 --k 。
2. 如果在快指针先走的过程中，快指针为NULL，那么我们直接返回，说明这个链表没有倒数 k 个结点。
3. 最后就让快慢指针一起走，结束的条件为 fast->next 为空时我们就停止，因为我们上述为了方便，我们只走了 k-1 步，所以这里我们要少走一步，为的是和上面的对应起来。
注意事项：首先我们正常情况下，是直接让快指针走k步，然后让快指针走到NULL时停止，但是我们有些极端情况使得我们不能走k步，所以我们这里选择走k-1步，然后在最后少走一步，走到快指针的next为NULL时就停止。还有就是我们要判断这个链表有没有倒数第k个节点，就是在快指针先走时，走的每一步都判断快指针是否为NULL，如果为NULL，那么就证明，快指针还没有走k-1步时，链表到头了，就证明链表没有倒数第 k 个节点。
21. 合并两个有序链表
5. 合并链表题目分析：
我们看图分析，首先两个链表都是升序，然后要求我们返回一个新的链表，并且也是升序的，所以我们就创建一个链表，然后同时遍历这两个链表，谁的值小，拿下来尾插，最后让剩余的链表链接到后面就好了。
代码实现：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* head = NULL; struct ListNode* tail = NULL; head = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); head->next = NULL; while(list1 && list2) { if(list1->val val) { tail->next = list1; tail = list1; list1 = list1->next; } else { tail->next = list2; tail = list2; list2 = list2->next; } } if(list1) { tail->next = list1; } if(list2) { tail->next = list2; } struct ListNode* next = head->next; free(head); return next;}1. 首先我们创建链表，定义两个指针，分别指向头尾。
2. 接着我们同时遍历两个链表，循环结束的条件是两个链表有一个为空截止，继续的条件就是两个链表都不为空。
3. 遍历中比较值较小的拿下来尾插，让该链表向后移动。
4. 最后判断那个链表不为空，就链接到创建的链表的尾指针后面。
5. free掉头结点，防止内存泄漏。
注意事项：我们在循环条件处容易出错，还容易不考虑最后循环完的链表是否不为空，进行尾插，最后就是内存泄漏。
面试题 02.04. 分割链表
6.分割链表题目分析：
这道题简单来说就是把小于 x 的值放到 x 的前面，把大于 和 等于 x 的值放在后面，并且顺序不能打乱，比如 4 在 3 的前面，合并后也要 4 在 3的前面。所以我们采用两个链表，分别的插入小于 x 的和其他的元素，最后把两个链表合并一下。
代码实现：
struct ListNode* partition(struct ListNode* head, int x){ struct ListNode* Minhead, *Mintail, *Maxhead, *Maxtail; Minhead = Mintail = (struct ListNode*)malloc(sizeof(struct ListNode)); Maxhead = Maxtail = (struct ListNode*)malloc(sizeof(struct ListNode)); Maxhead->next = NULL; Minhead->next = NULL; struct ListNode* cur = head; while (cur) { if (cur->val next = cur; Mintail = Mintail->next; } else { Maxtail->next = cur; Maxtail = Maxtail->next; } cur = cur->next; } Mintail->next = Maxhead->next; Maxtail->next = NULL; struct ListNode* Newhead = Minhead->next; free(Minhead); free(Maxhead); return Newhead;}1. 首先我们创建两个带头的链表，和一个遍历指针 cur。
2.然后遍历分别插入链表即可。
3. 我们把链表连接起来时，首先我们的链表是带头的，所以我们要跳过头节点，并且我们的Max链表的最后一个元素不一定为NULL，我们要手动置为NULL。
4.我们返回时，保存节点时也要跳过头指针，然后一个个free掉空间
注意：太多的节点不要使用错误啦。