数据结构链表2（常考习题1）（C语言）
移除链表元素：
. - 力扣（LeetCode）
题目：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
解题思路：
情况1：
情况2：
情况3：
我们以第一种情况写代码：
ListNode* removeElements(ListNode* head, int val)
{ListNode* cur = head;ListNode* slow = head;while (cur){if (cur->val == val){ListNode* tmp = cur->next;free(cur);cur = tmp;slow->next = cur;}else{slow = cur;cur = cur->next;}}
}以第二、三种特殊情况改代码：
如果第一次就要删除头：
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;struct ListNode* tmp = NULL;struct ListNode* slow = head;while (cur){if (cur->val == val){tmp = cur->next;if(head->val == val){free(cur);cur = tmp;head = cur;slow = head;}else{free(cur);cur = tmp;slow->next = cur;}}else{slow = cur;cur = cur->next;}}return head;
}反转链表：
. - 力扣（LeetCode）
题目：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解题思路：
考虑特殊：
只有一个元素：
同样适用！！
双指针解题，一个前驱指针，一个指向head的指针，还有一个临时变量next为了记录head的next的值。
具体代码如下：
ListNode* reverseList(ListNode* head)
{ListNode* cur = head;ListNode* slow = NULL;ListNode* next = NULL;while (cur){next = cur->next;cur->next = slow;slow = cur;cur = next;}
}链表的中间节点：
. - 力扣（LeetCode）
题目：
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
解题思路：
利用快慢指针，有四种情况，如图所示：
第一种，链表个数为偶数时：
第二种，链表个数为奇数时：
第三种，链表个数为1个时：
第四种，链表个数为2个时：
综上：
得出结论：
1、当链表个数大于2时，且为偶数时：当快指针的next走到NULL时，慢指针所在的地方就是中间结点的地方。
2、当链表个数大于2时，且为奇数时：
当快指针走到NULL时，慢指针所在的地方就是中间节点的地方。
3、当链表个数等于1时：
快指针和慢指针不需要走。
4、当链表个数为2时：
和情况一是一样的。
综上：
也就是快指针分两种情况：
第一种就是快指针自身到达NULL时，第二种就是快指针的next到达NULL时。
不论是那种情况，最终都返回慢指针！！
代码如下：
ListNode* middleNode(ListNode* head)
{ListNode* fast = head;ListNode* slow = head;while (fast){if (fast->next == NULL){return slow;}fast = fast->next->next;slow = slow->next;}return slow;
}合并两个有序链表：
. - 力扣（LeetCode）
题目：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：
两个链表，每个链表都有一个可以移动的指针，接着让一个指针移动，每移一步让两个指针指向的值做对比，小的移下来，然后让新链表的指针和刚刚移动过的俩把表指针往后走一步。
直到其中一个链表的指针指向空之后，将另一个链表的剩下部分整体移过去！
画图很重要！！！
特殊考虑：
如果其中一个链表为空，可以指直接返回另一个链表的地址！
代码如下：
画图很重要！！！！！！
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* cur1 = list1;struct ListNode* cur2 = list2;struct ListNode* newhead = NULL;struct ListNode* tmp = NULL;if (cur1 == NULL){return cur2;}else if(cur2 == NULL){return cur1;}while (cur1 && cur2){if (cur1->val > cur2->val){if (newhead == NULL){newhead = tmp = cur2;}else{tmp->next = cur2;tmp = tmp->next;}cur2 = cur2->next;}else{if (newhead == NULL){newhead = tmp = cur1;}else{tmp->next = cur1;tmp = tmp->next;}cur1 = cur1->next;}}if (cur1 == NULL){tmp->next = cur2;}else{tmp->next = cur1;}return newhead;
}链表分割：
链表分割_牛客题霸_牛客网
题目：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
解题思路：
将比x大的和比x小的首先区分开，最后再将其合并在一起！！
注意：最后比x大的后面需要手动在末尾添加NULL指针！
考虑特殊：
如果链表中没有比x大的数，或者没有比x小的数，此时直接返回原链表的地址！！
代码如下：
ListNode* partition(ListNode* pHead, int x)
{ListNode* cur = pHead;ListNode* newhead1 = NULL;ListNode* tmp1 = NULL;ListNode* newhead2 = NULL;ListNode* tmp2 = NULL;while (cur){if (cur->val > x){if (newhead1 == NULL){newhead1 = tmp1 = cur;}else{tmp1->next = cur;tmp1 = tmp1->next;}}else{if (newhead2 == NULL){newhead2 = tmp2 = cur;}else{tmp2->next = cur;tmp2 = tmp2->next;}}cur = cur->next;}if (!(newhead1 && newhead2)){return pHead;}tmp1->next = NULL;tmp2->next = newhead1;return newhead2;
}链表的回文结构：
链表的回文结构_牛客题霸_牛客网
题目：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1返回：true
解题思路：
文字叙述：
只需要将该链表进行反转后，然后两个链表进行遍历，如果中途有不一样的值就输出fasle如果遍历结束后，两个指针都指向NULL，返回true，就可以说明该链表是回文结构。
具体代码：
ListNode* Reverse(ListNode*head)//链表反转代码
{ListNode* cur = head;ListNode* slow = NULL;while (cur){ListNode* tmp = cur->next;cur->next = slow;slow = cur;cur = tmp;}return slow;
}bool chkPalindrome(ListNode* pHead) //判断回文代码{ListNode* cur = pHead;ListNode* newhead = NULL;newhead = Reverse(cur);while (cur&&newhead){if(cur->val != newhead->val){return false;}cur = cur->next;newhead = newhead->next;}return true;// write code here}
！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！