目录
一、移除链表元素
二、找出链表的中间节点
三、合并两个有序链表
四、反转链表
五、求链表中倒数第k个结点
六、链表分割
七、链表的回文结构
八、判断链表是否相交
九、判断链表中是否有环(一)
十、 判断链表中是否有环(二)
注：第六题和第七题牛客没有C环境，我在C++环境下用C语言写这道题（目前还没学C++，请大佬们理解一下，理解万岁！！）
一、移除链表元素
203. 移除链表元素 - 力扣（LeetCode）
- 给你一个链表的头节点
head和一个整数val- 请你删除链表中所有满足
Node.val == val的节点，并返回 新的头节点 。示例 1：
输入：head = [1, 2, 6, 3, 4, 5, 6], val = 6 输出：[1, 2, 3, 4, 5]
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* prev = NULL, * cur = head;
while (cur) {
if (cur->val == val) {
if (prev) {
prev->next = cur->next;
free(cur);
cur = prev->next;
}
else {
cur = head->next;
free(head);
head = cur;
}
}
else {
prev = cur;
cur = cur->next;
}
}
return head;
}思路：链表常规删除，注意删除头节点的情况。
1、创建指向当前节点的前一个节点的指针prev=NULL（头节点的前一个节点为空），指针cur指向链表头节点。
2、以当前节点cur不为空为循环执行条件，判断当前节点的值是否等于val，等于则进行删除，不等于则prev更新为当前节点cur，当前节点cur指向下一个节点。
3、当前节点的值等于val时：
- 如果值为
val的节点不在头节点（prev不为NULL），将prev的next指针指向当前节点的下一个节点，然后释放当前节点并更新。- 如果值为
val的节点在链表头节点（prev为NULL），则释放原来的头节点，将head更新为当前节点的下一个节点。
下面是第二种方法，创建新的链表，把不删除的节点链接到新链表 ：
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* cur = head; // 当前遍历节点
struct ListNode* newhead = NULL; // 新链表的头节点
struct ListNode* tail = NULL; // 新链表的尾节点
while (cur) {
if (cur->val != val) { // 当前节点的值不等于要删除的值
if (tail == NULL) { // 第一次插入
newhead = tail = cur; // 设置新链表的头和尾
}
else {
tail->next = cur; // 将当前节点连接到新链表的尾部
tail = tail->next; // 更新新链表的尾节点
}
cur = cur->next; // 移动到下一个节点
tail->next = NULL; // 断开新链表的尾节点连接
}
else {
struct ListNode* del = cur; // 保存需要删除的节点
cur = cur->next; // 移动到下一个节点
free(del); // 释放需要删除的节点的内存
}
}
return newhead; // 返回新链表的头节点，已移除所有值为 val 的节点
}
二、找出链表的中间节点
876. 链表的中间结点 - 力扣（LeetCode）
给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* fast = head, * slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}思路：快慢双指针
1、采用速度为1步的slow和速度为2步的fast，这样设置二者速度比较合理。
2、循环结束的条件需要考虑一下，分为链表节点个数为奇数和偶数，当fast走到最后的结果如下：
3、 所以循环结束的条件为 fast && fast->next 二者有一个为空。
三、合并两个有序链表
21. 合并两个有序链表
- 将两个升序链表合并为一个新的 升序 链表并返回。新
- 链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
struct ListNode* tail = NULL, * head = NULL;
while (list1 && list2) {
if (list1->val < list2->val) {
if (tail == NULL) {
head = tail = list1;
}
else {
tail->next = list1;
tail = tail->next;
}
list1 = list1->next;
}
else {
if (tail == NULL) {
head = tail = list2;
}
else {
tail->next = list2;
tail = tail->next;
}
list2 = list2->next;
}
}
if (list1)
tail->next = list1;
if (list2)
tail->next = list2;
return head;
}思路：创建新链表，较小的进行链接。
好像跟顺序表的题相像合并两个有序数组
不过，这次是单链表，所以我们可以创建新链表，从前向后将较小的链接到链表中，不需要从后先前了。
1、首先判断是否有链表为空，一个链表为空，则直接返回合并后的结果：另一个不为空的链表，都为空则返回任意一个链表。
2、创建新链表的尾节点tail和头节点head，初始化为空。
3、比较 list1 和 list2 当前节点的值。
- 如果 list1 的当前节点值小于 list2 的当前节点值，将 list1 的节点添加到合并后的链表中。
- 如果 list2 的当前节点值小于等于 list1 的当前节点值，将 list2 的节点添加到合并后的链表中。
4、在向合并链表中添加节点时，需要检查 tail 是否为 NULL，
- 如果是，说明这是第一个节点，因此同时更新 head 和 tail。
- 否则，只需将新节点连接到 tail 的 next 并将 tail 更新为新节点。
5、每次添加节点后，对应的链表list需要向后移动一位。
6、最终循环结束时，如果有链表不为空，证明该链表剩余节点的值均大于另一个链表的最大值，则将该链表其余的节点依次插入新链表。
7、返回新链表头节点head。
四、反转链表
206. 反转链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
思路(一)： 创建新链表，从前向后取出原链表的节点进行头插。
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* cur = head;
struct ListNode* rhead = NULL;
while (cur) {
struct ListNode* next = cur->next;
cur->next = rhead;
rhead = cur;
cur = next;
}
return rhead;
}1. 开始时，定义两个指针 `cur` 和 `rhead`。
- `cur` 指向原始链表的头部 `head`
- `rhead` 用来构建反转后的链表，初始为空，表示反转后链表的尾部。
2. 进入循环，这个循环将遍历整个链表并进行反转操作。循环的条件是 `cur` 不为 NULL，表示还有节点需要处理。
3. 在循环内部，首先创建一个临时指针 `next` 来保存 `cur` 的下一个节点，因为在修改 `cur->next` 指针之前，需要先保存下一个节点的信息，否则会丢失对它的引用。
4. 接着，将 `cur->next` 指向 `rhead`，这一步实际上是将 `cur` 的下一个节点指向反转后链表的头部，从而将 `cur` 从原链表中分离出来。
5. 更新 `rhead` 为 `cur`，这一步将 `cur` 成为反转后链表的新头部。
6. 更新 `cur` 为 `next`，这一步将 `cur` 移动到原链表中的下一个节点，准备处理下一个节点。
7. 循环继续执行，直到 `cur` 变为 NULL，表示已经遍历完整个链表。此时，`rhead` 指向反转后链表的头部。
8. 返回 `rhead`，它现在指向反转后的链表的头部，完成链表的反转。
思路(二)：调转链表方向（三指针）
-
n1初始化为 NULL，表示反转后的链表的尾部。 -
n2初始化为链表的头部节点head。 -
n3初始化为n2的下一个节点，即n2->next。
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、进入循环，这个循环将遍历整个链表并反转节点。
2、在循环内部，首先将
n2的next指针指向n1，这是为了将n2的指针方向反转，将其指向前一个节点n1，而不是原来的下一个节点。
3、接着更新
n1和n2，将它们分别向前移动一个节点。n1移动到n2的位置，n2移动到n3的位置。
4、继续检查
n3是否为 NULL。如果n3不为 NULL，将n3移动到它的下一个节点，以便在下一轮循环中使用。
5、循环继续执行，直到
n2为 NULL，表示已经遍历完整个链表。此时，n1指向原链表的最后一个节点，它成为了反转后链表的头部。
6、返回
n1，它现在指向反转后的链表的头部，完成了链表的反转。
五、求链表中倒数第k个结点
链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
输入一个链表，输出该链表中倒数第k个结点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
struct ListNode* slow=pListHead,*fast=pListHead;
while(k){
if(fast==NULL)
return 0;
fast=fast->next;
k--;
}
while(fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}思路： 快慢指针
快慢指针的速度都为1步，快指针先走k步，然后慢指针开始与快指针同时走，快指针走到最后为空时，慢指针则为倒数第k个节点。
1、通过while循环先让fast走k步，如果fast为空则无法求出倒数第k个节点（k大于链表长度）返回值为0。
2、第二个while循环slow和fast开始同时向后走，fast为空时，slow指向的节点即为所求倒数第k个节点。
六、链表分割
链表分割_牛客题霸_牛客网 (nowcoder.com)
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;
lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = pHead;
while (cur) {
if (cur->val < x) {
lesstail->next = cur;
lesstail = lesstail->next;
}
else {
greatertail->next = cur;
greatertail = greatertail->next;
}
cur = cur->next;
}
lesstail->next = greaterhead->next;
greatertail->next = NULL;
pHead = lesshead->next;
free(lesshead);
free(greaterhead);
return pHead;
}
}; 思路：假设x=5，链表各节点值为
如下图：
1、创建变量* lesshead, * lesstail为小于x的链表的头节点和尾节点,
* greaterhead, * greatertail 为大于x的链表的头节点和尾节点。
- 为两个新链表头节点开辟空间，储存值val和指向下一个节点next。
2、在循环中判断cur的值是否小于x，小于则将cur链接到less链表，不小于则链接到grearter链表。
3、两个新链表需要链接合并成完整链表。
4、greatertail->next = NULL；
- 这一步一定不能少，否则可以会出现循环链表：
七、链表的回文结构
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* cur=head,*rhead=NULL;
while(cur){
struct ListNode* next=cur->next;
cur->next=rhead;
rhead=cur;
cur=next;
}
return rhead;
}
bool chkPalindrome(ListNode* head) {
struct ListNode* mid=middleNode(head);
struct ListNode* rmid=reverseList(mid);
while(rmid){
if(rmid->val==head->val){
rmid=rmid->next;
head=head->next;
}
else{
return false;
}
}
return true;
}
};思路：从中间点开始逆置， 从头节点和中间节点开始分别往后进行比较。
1、middleNode函数用于找到中间节点，具体讲解参考二、找出链表的中间节点 。
2、
reverseList函数用于逆置链表，具体讲解参考四、反转链表。
3、
chkPalindrome函数中首先指针mid指向中间节点，指针rmid指向从中间节点到最后逆置后的新的中间节点，循环遍历rmid，rmid与头结点head从前往后依次比较，如果有不相同的值，则返回false，否则返回true，rmid走到链表时(即rmid为空时)，循环结束。
八、判断链表是否相交
160. 相交链表
给你两个单链表的头节点
headA和headB
- 请你找出并返回两个单链表相交的节点。
- 如果两个链表不存在相交节点，返回
null。图示两个链表在节点
c1开始相交：
- 题目数据 保证 整个链式结构中不存在环。
- 注意，函数返回结果后，链表必须 保持其原始结构 。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode * tailA=headA;
struct ListNode * tailB=headB;
int lenA=1,lenB=1;
while(tailA->next){
tailA=tailA->next;
lenA++;
}
while(tailB->next){
tailB=tailB->next;
lenB++;
}
if(tailA!=tailB){
return NULL;
}
int gap=abs(lenA-lenB);
struct ListNode * longList=headA;
struct ListNode * shortList=headB;
if(lenA<lenB){
longList=headB;
shortList=headA;
}
while(gap--){
longList=longList->next;
}
while(longList!=shortList){
longList=longList->next;
shortList=shortList->next;
}
return longList;
}思路：长的链表走相差长度步数，然后短的开始和长的同时走，节点地址相等则相交。
1、定义变量 tailA 和 tailB 分别指向链表A和B的头节点，分别遍历对应链表获得链表长度lenA和lenB，因为while循环结束条件是tail->next为空，所以len的值初始化为1。
2、通过比较
tailA和tailB是否相等来判断两个链表的尾节点是否一致。如果不相等，说明两个链表不可能有公共节点，直接返回NULL。
3、使用abs函数求出链表A与B长度差值，差值赋值给变量gap。
4、 创建两个指针longlist和shortlist分别指向链表A和B的头节点，然后判断链表大小，如果lenA大于lenB，则 longList=headB，否则 shortList=headA。
5、 longlist先向后走gap步，为了保持和shortlist同步遍历。
6、longlist和shortlist同时向后遍历，当二者相等时，停止遍历返回二者任意一个即为两个单链表相交的起始节点。
九、判断链表中是否有环(一)
141. 环形链表
给你一个链表的头节点
head，判断链表中是否有环。注意：
pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回
true。 否则，返回false。示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
bool hasCycle(struct ListNode *head) {
struct ListNode *fast=head;
struct ListNode *slow=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
return true;
}
return false;
}思路：快慢指针
指针slow一次走一步，指针fast一次走两步，这样在链表中走，如果有环存在则二者一定会相遇，因为fast是slow速度的两倍。如果fast走到最后为空，证明该链表没有环存在。
当fast步数
十、 判断链表中是否有环(二)
142. 环形链表 II
给定一个链表的头节点
head
返回链表开始入环的第一个节点。
如果链表无环，则返回
null。不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
struct ListNode* detectCycle(struct ListNode* head) {
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) {
struct ListNode* meet = slow;
while (head != meet) {
head = head->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}思路：快慢指针
slow一次走一步，fast一次走两步，他们都从头节点head位置开始移动。
设head到入环节点的距离为L，假设第一次相遇位置为meet，入环节点到meet的距离为X，相遇位置到入环节点的距离为环的周长C减去X。
slow走的路程：L+X
fast走的路程： L+X+n*C（slow进环前，fast走了n圈，比如：环很小则fast可能走了好几圈slow才进环）。
因为fast的速度是slow的两倍，所以fast走的路程是slow的两倍，一圈之内fast一定追上slow！！
由此可以得到以下关系式：2(L+X)=L+X+n*C
化简得到：L=n*C-X 即 L=(n-1)C+C-X，文章来源：https://www.toymoban.com/news/detail-738584.html
这样就知道了 L=C-X，即一个指针从相遇点开始走，一个指针从头节点开始走，他们会在入环点相遇。文章来源地址https://www.toymoban.com/news/detail-738584.html
到了这里，关于解剖—单链表相关OJ练习题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
