一、移除链表元素
题目链接
题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点。
思路1
遍历链表，比对每一个节点的数据与val是否相等，如果相等，就free掉该节点。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、当链表的头结点的数据等于val时，我们free掉该节点后需要挪动head指针，让其指向新的头结点；
2、我们在遍历链表的时候需要记录前一个节点的地址，因为当我们free掉当前节点之后，我们要让前一个节点的next；链接到当前节点的下一个节点；
代码实现
//法一：遍历链表，找到等于val的节点就free掉 struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur = head, *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; }
思路2
遍历链表，将不等于val的节点尾插到一个新的链表，将等于val的节点free掉。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、由于我们是把原链表中的节点尾插到新链表中去，所以我们插入元素的时候需要判断链表是否为空，如果为空，我们需要改变新链表的头结点；
2、当然，我们也可以把我们的新链表设计为带哨兵位的，这样我们直接进行尾插就行，但是要注意我们返回的应该是guard->next，因为哨兵位头结点不用于存储数据，同时在return之前记得把哨兵位头结点释放掉；
3、由于原链表中最后一个节点的数据可能等于val，所以我们需要将新链表中尾结点的next置为NULL，防止通过它来访问已经被释放掉的节点。
代码实现
//法二：取不等于val的节点尾插 struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode)); //哨兵位头结点 guard->next = NULL; //当原链表为空时我们可以正常返回 struct ListNode* tail = guard, *cur = head; while(cur) { if(cur->val == val) //移除 { struct ListNode* next = cur->next; free(cur); cur = next; } else //尾插 { tail->next = cur; tail = cur; cur = cur->next; } } tail->next = NULL; //避免当最后一个元素别移除时前面还保留它的地址，造成野指针 head = guard->next; free(guard); guard = NULL; return head; }
二、反转链表
题目链接
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
思路分析
思路1
反转每一个节点的指向：定义三个节点指针prev cur next，最开始让prev指向NULL，cur指向head，next指向cur->next，然后让cur->next指向prev，最后进行迭代，即让prev=cur、cur=next、next=cur->next，直到cur为空时循环结束，此时prev为反转后的链表的头结点。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、我们需要定义一个next变量来保存下一个节点的地址，因为当我们让当前节点指向前一个节点时，我们会丢失下一个节点的地址；
2、当cur->next为NULL时，我们再将cur->next=prev，然后cur=next，此时所有节点反转完毕，cur==NULL，循环结束；
代码实现
//法一：让每一个节点指向它的前一个节点（三指针） struct ListNode* reverseList(struct ListNode* head){ struct ListNode* prev = NULL, *cur = head, *next = NULL; while(cur) { //翻转节点的指向 next = cur->next; cur->next = prev; //迭代 prev = cur; cur = next; } return prev; //此时尾结点是新的头节点 }
思路2
将原链表中的节点头插到新链表中，然后返回新链表的头。时间复杂度：O(N) 空间复杂度：O(1)
易错点
如果我们的链表不带头，我们每头插一个元素都需要改变头结点。
代码实现
//法二：取出链表的每一个节点头插 struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newhead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; }
三、链表的中间节点
题目链接
题目描述
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。时间复杂度：O(N) 空间复杂度：O(1)
思路分析
思路1
遍历两遍数组，第一遍求出链表长度，第二步找出链表的中间节点并返回。
代码实现
//法一：遍历两次链表，第一次找出链表有几个节点，第二次返回链表的中间节点 struct ListNode* middleNode(struct ListNode* head){ struct ListNode* cur = head; int count = 0; while(cur) { count++; cur = cur->next; } cur = head; count /= 2; while(count--) { cur = cur->next; } return cur; }
思路2
由于这道题用第一种方法实现十分简单，所以在面试中面试官会加一个限制条件：要求只能遍历一遍链表；这时候就只能用快慢指针来解题了；
快慢指针：定义两个指针 – fast slow，慢指针一次走一步，快指针一次走两步；当链表长度为奇数，fast->next == NULL时，slow 为中间节点；当链表长度为偶数，fast == NULL 时，slow 为中间节点。时间复杂度：O(N) 空间复杂度：O(1)
易错点
我们在写while循环的条件时，必须写成 fast && fast->next，不能写成 fast->next && fast，因为当链表长度为偶数时，后面这种写法会发生空指针的解引用。
代码实现
//法二：使用快慢指针，slow一次走一步，fast一次走两步，只遍历一遍数组 //奇数个节点时，当fast->next == NULL时，slow刚好到达中间节点 //偶数个节点时，当fast == NULL时，slow刚好达到中间节点 struct ListNode* middleNode(struct ListNode* head){ struct ListNode* fast, *slow; slow = fast = head; //注意：while条件中fast一定要写前面，不然偶数个时fast->next会造成空指针解引用 while(fast && fast->next) //节点是奇数还是偶数未知注意： { slow = slow->next; fast = fast->next->next; } return slow; }
四、链表中倒数第K个节点
题目链接
链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路分析
思路1也是遍历两遍链表，和上面题一样，这里我直接阐述思路2，思路2也是利用快慢指针的思想；O(N) 空间复杂度：O(1)
快慢指针：定义两个指针 – fast slow，先让 fast 走K/K-1步，然后让 fast 和 slow 一起走； fast 先走K步时，当 fast == NULL，slow 为倒数第K个元素；fast 先走K-1步时，当 fast->next == NULL，slow 为倒数第K个元素；这里与链表长度为奇数或者偶数无关。
易错点
注意：在做OJ类题目时，我们要考虑测试用例的边界情况，比如K等于1，K等于链表长度；还需要考虑测试用例的极端情况，比如链表为空，K为0，K大于链表长度；
在这道题中，我们正常编写的代码一般来说对于边界情况是能够正常通过的，对于极端情况中的NULL，K等于0也是能够通过的，但是K大于链表长度的情况很可能会被我们忽略；
当K大于链表长度时，如果我们 在K-- 的 while 循环中没有对 fast进 行空指针检查的话，那么 fast 会不断往后走，直到 fast == NULL 时仍然不会停下，这时候就会造成对空指针解引用的问题。
代码实现
//法二：快慢指针：让fast先走K/k-1步，然后slow和fast同时走，这时fast和slow之间就相差K/k-1个节点 //当fast先走K步时：fast == NULL //当fast先走K-1步时：fast->next == NULL struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* fast, *slow; fast = slow = pListHead; while(k--) //让fast先走K步 { if(fast == NULL) { return NULL; } fast = fast->next; } while(fast) { fast = fast->next; slow = slow->next; } return slow; }
五、合并两个有序链表
题目链接
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路分析
这道题的解题思路和顺序表中的合并两个有序数组的思路一模一样，只是这里尾插的是节点而已。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、由于我们是把原链表中的节点尾插到新链表中去，所以我们插入元素的时候需要判断链表是否为空，如果为空，我们需要改变新链表的头结点；
2、当然，我们也可以把我们的新链表设计为带哨兵位头的，这样我们直接进行尾插就行，但是要注意我们返回的应该是guard->next，因为哨兵位头结点不用于存储数据，同时在return之前我们要记得把哨兵位头结点释放掉；
代码实现
//取小的节点尾插 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode)); //哨兵位 guard->next = NULL; struct ListNode* tail = guard, *cur1 = list1, *cur2 = list2; while(cur1 && cur2) //取小的尾插 { if(cur1->val < cur2->val) { struct ListNode* next = cur1->next; tail->next = cur1; tail = cur1; //更新尾 cur1 = next; } else { struct ListNode* next = cur2->next; tail->next = cur2; tail = cur2; cur2 = next; } } //链接剩余的节点 if(cur1) tail->next = cur1; if(cur2) tail->next = cur2; struct ListNode* head = guard->next; free(guard); guard = NULL; return head; }
六、分隔链表
题目链接
面试题 02.04. 分割链表 - 力扣（LeetCode）
题目描述
分隔链表分为初阶版和进阶版，初阶版不要求我们保留每个分区中各节点的初始相对位置，而进阶版则要求要求我们保留每个分区中各节点的初始相对位置，这里我们讲解进阶版。
思路分析
思路1
取原链表中val小于x的节点节点头插，val大于x的节点尾插；此方法会改变链表中节点的初识相对位置，只适用于初阶。时间复杂度：O(N) 空间复杂度：O(1)
思路2
将原链表中val小于x的节点尾插到一个新链表中，将val大于x的节点尾插到另一个新链表中，最后将两个新链表链接起来。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、我们可以将两个新链表设计为带头链表，这样可以免去插入第一个元素时的判断步骤，避免犯错；
2、我们需要将用于链接val大于x的链表的尾结点的next置空，避免最后一个节点的val小于x时前一个节点的next仍指向它，从而形成环。
代码实现
//把大于等于X的节点和小于X的节点分别尾插到新的链表中，然后再把两个链表链接起来 struct ListNode* partition(struct ListNode* head, int x){ //开辟两个链表的头结点 struct ListNode* lessGuard = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* greaterGuard = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* lessTail = lessGuard, *greaterTail = greaterGuard, *cur = head; lessGuard->next = NULL; greaterGuard->next = NULL; while(cur) { if(cur->val < x) //如果小于X就尾插到less中 { lessTail->next = cur; lessTail = cur; } else //否则就尾插到greater中 { greaterTail->next = cur; greaterTail = cur; } cur = cur->next; } //让less的尾结点链接到greater的头结点 lessTail->next = greaterGuard->next; //把greater的头结点置空，防止当最后一个元素小于X被尾插到less时仍然指向它，从而形成环，造成死循环 greaterTail->next = NULL; head = lessGuard->next; //释放哨兵位头结点 free(greaterGuard); free(lessGuard); greaterGuard = NULL; lessGuard = NULL; return head; }
