1.移除链表元素
题目链接：https://leetcode.cn/problems/remove-linked-list-elements/description/
题目思路：创建一个新的链表，链表头为newHead,链表尾为newTail,再创建一个指针变量遍历原链表，把值不为val的结点进行尾插，注意，如果我们在结束循环时，要把newTail->next=NULL,否则会报错。
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newHead, * newTail, * pcur;
pcur = head;
newHead = newTail = NULL;
while (pcur)
{
if (pcur->val != val)
{
if (newHead == NULL)
{
newHead = newTail = pcur;
}
else
{
newTail->next = pcur;
newTail = newTail->next;
}
}
pcur = pcur->next;
}
if(newTail)
{
newTail->next = NULL;
}
return newHead;
}
这个代码可以通过，但是为什么我们没单独讨论链表为空的情况？1.我们如果在开始加判断是否为空的情况，确实可以避免原链表为空的情况，但是我们如果像if(newTail)的判断，则如果链表为空的情况，newTail本来为NULL,这样就不用分情况讨论了。2.如果我们原链表的所有val都为val,则我们新链表为空，这种情况我们还要再判断一次，所以我们干脆直接只判断newTail是否为NULL就可以了，所以那个if不能省略。即使新链表为空，也会正确得出结果。
2.反转链表
题目链接：https://leetcode.cn/problems/reverse-linked-list/description/
思路1：我们可以像上题一样通过创建新链表的方式来反转链表，但是这样如何改？
首先我们需要一个空链表为newHead,这个newHead一直在变，而我们需要创建一个指针pre，这个指针pre指向这个新链表的下一个结点，这个指针初始化为NULL,然后再创建一个指针遍历原链表，这个指针相对于newHead,开始循环的时候就已经走向了newHead->next,这个然后再把newHead->next指向pre，最后再把pre赋值为newHead，然后再把之前保存的newHead->next的指针赋值给newHead,代码如下：
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newHead = head, * pre = NULL;
while (newHead)
{
struct ListNode* save = newHead->next;
newHead->next = pre;
pre = newHead;
newHead = save;
}
return pre;
}
思路2：创建三个指针，n1为NULL，n2为head,n3-=n2->next,然后n1先走到n2,n2走到n3,n3指向n3的下一个结点，n1为头结点，代码如下：
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL)
{
return head;
}
struct ListNode* n1, * n2, * n3;
n1 = NULL;
n2 = head;
n3 = head->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
//n3 = n3->next;
//不能这样写，如果n3到原链表的尾结点，就不存在n2->next了
if (n3)
{
n3 = n3->next;
}
}
return n1;
}
3.链表的中间结点
题目链接：https://leetcode.cn/problems/middle-of-the-linked-list/description/
我们如何找中间结点：
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast, * slow;
fast = slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
但是我们要注意一个问题，我们可以把循环条件里面的fast和fast->next调换位置吗？
这个不行，如果调换位置，如果fast为NULL，就没有fast->next了，所以我们不能这样，&&是从左往右执行的，如果前面条件不成立就不会执行第二个条件的判断
4.合并两个有序链表
题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/
如何合并？
创建一个新链表，然后比较两个链表的首结点所存储的数据，然后把这个比较小的数据的结点进行尾插，注意：最后我们需要把没有插入的结点进行尾插。如果有个链表为空，我们直接返回另外一个链表的首结点。有：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if (list1 == NULL)
{
return list2;
}
if (list2 == NULL)
{
return list1;
}
struct ListNode* l1, * l2, * newHead, * newTail;
l1 = list1;
l2 = list2;
newHead = newTail = NULL;
while (l1 && l2)
{
if (l1->val < l2->val)
{
if (newHead == NULL)
{
newHead = newTail = l1;
}
else
{
newTail->next = l1;
newTail = newTail->next;
}
l1 = l1->next;
}
else
{
if (newHead == NULL)
{
newHead = newTail = l2;
}
else
{
newTail->next = l2;
newTail = newTail->next;
}
l2 = l2->next;
}
}
if (l1)
{
newTail->next = l1;
}
else
{
newTail->next = l2;
}
return newHead;
}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if (list1 == NULL)
{
return list2;
}
if (list2 == NULL)
{
return list1;
}
struct ListNode* l1, * l2, * newHead, * newTail;
l1 = list1;
l2 = list2;
newHead = newTail = (struct ListNode*)malloc(sizeof(struct ListNode));
while (l1 && l2)
{
if (l1->val < l2->val)
{
newTail->next = l1;
newTail = newTail->next;
l1 = l1->next;
}
else
{
newTail->next = l2;
newTail = l2;
l2 = l2->next;
}
}
if (l1)
{
newTail->next = l1;
}
else
{
newTail->next = l2;
}
newTail = newHead->next;
//但是我们的头结点不是有效的，所以我们不能直接返回newHead,要保存其下一个结点
free(newHead);
newHead = NULL;
return newTail;
}
5.链表分割
题目链接：https://nowcoder.com/practice/0e27e0b0de4eacac178676ef9c9d70
不要看这个代码只能用C++或Java写，但是C与C++差不多，如果要按照我的写法，要把语言改为C++
ListNode* smallHead, * smallTail, * bigHead, * bigTail;
smallHead = smallTail = (ListNode*)malloc(sizeof(ListNode));
bigHead = bigTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* pcur = pHead;
while (pcur)
{
if (pcur->val < x)
{
smallTail->next = pcur;
smallTail = smallTail->next;
}
else
{
bigTail->next = pcur;
bigTail = bigTail->next;
}
pcur = pcur->next;
}
今天就讲5个题目，我们不是解决这一个题目这么简单，要学会这里面的算法，不能只解决完题目就可以了，我们也要知道其中的含义。12.30我将发布下一个单链表题目的解答。喜欢的可以一键三连哦。所有代码如下，要的自取：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
struct ListNode* removeElements(struct ListNode* head, int val)
{
if (head == NULL)
{
return head;
}
struct ListNode* newHead, * newTail, * pcur = head;
newHead = newTail = NULL;
while (pcur)
{
if (newHead == NULL)
{
newHead = pcur;
newTail = pcur;
}
else
{
newTail->next = pcur;
newTail = newTail->next;
}
pcur = pcur->next;
}
newTail->next = NULL;
return newHead;
}
struct ListNode* removeElements(struct ListNode* head, int val)
{
if (head == NULL)
{
return head;
}
struct ListNode* newHead, * newTail, * pcur;
pcur = head;
newHead = newTail = NULL;
while (pcur)
{
if (pcur->val != val)
{
if (newHead == NULL)
{
newHead = newTail = pcur;
}
else
{
newTail->next = pcur;
newTail = newTail->next;
}
}
pcur = pcur->next;
}
newTail->next = NULL;
return newHead;
}
struct ListNode* removeElements(struct ListNode* head, int val)
{
