一、移除链表元素
题目描述：力扣
法一：直接循环依次判断
对于这个题目，我们最容易想到的一种思路就是，直接遍历链表，当链表的值是需要删除的时候，直接删除即可，然后改变连接关系即可
代码如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur=head; struct ListNode* prev=NULL; while(cur!=NULL) { if(cur->val!=val) { prev=cur; cur=cur->next; } else { if(head==cur) { head=cur->next; free(cur); cur=head; } else { struct ListNode* next=cur->next; free(cur); prev->next=next; cur=next; } } } return head; }
对于我们写的这个代码，我们有以下几点需要注意：
1.当头结点就是需要删除的时候，那么prev是为空的，所以我们需要特殊处理，采用头删的思路即可。
2.这个函数传递的是一级指针，而非二级指针，原因是题目要求最后返回了头结点。所以可以不使用二级指针。
3.当代码出现问题，而在力扣上无法肉眼观察出错误的时候，我们就需要放到vs上进行调试，那么就涉及到需要自己手搓一个链表的问题，手搓的方法如下所示
int main() { struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode)); n1->val = 1; n2->val = 2; n3->val = 3; n4->val = 4; n1->next = n2; n2->next = n3; n3->next = n4; n4->next = NULL; }
法二：尾插法
这个方法的思路是这样的，我们重新定义一个链表，这个链表使用两个结点指针来控制，一个是头节点newhead,另一个是尾结点tail。一开始让他们都为空，即这个链表是空链表
然后我们在使用一个结点指针cur来遍历原来的链表，如果此处的值不是val，那就将这个结点尾插到新链表上。然后让尾结点向后走，cur结点也向后走。注意当第一个结点插入的时候，由于tail为空，所以特殊处理，直接赋值，然后使cur向后走即可
如果某处的值确实是val，那么就要设置一个新结点next去接收cur的下一个结点，然后释放cur。然后让tail的下一个结点赋值为cur。注意，这里还有一个特殊情况是，当题目所给的链表全要被删除的时候，由于tail为空，所以无法让tail的下一个结点赋值为cur。这里我们直接使用一个if排除掉这种情况即可
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* newhead=NULL; struct ListNode* tail=NULL; struct ListNode* cur=head; while(cur!=NULL) { if(cur->val!=val) { if(newhead==NULL) { newhead=cur; tail=cur; cur=cur->next; } else { tail->next=cur; tail=cur; cur=cur->next; } } else { struct ListNode* next=cur->next; free(cur); cur=next; if(tail!=NULL) tail->next=cur; } } return newhead; }
二、链表的中间结点
题目描述：力扣
解一：
对于这道题，我们最容易想到的思路就是，先遍历一遍，得到链表的长度，然后除2，就能得到要到达中间结点的长度。然后再一次遍历就能解出
解二：快慢指针
对于这道题，还有一种比较好的方法就是，一开始定义两个结点指针，然后一个一次走一步，另外一个一次走两步，如此一来，慢的那个指针恰好就是中间结点。具体代码如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ 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; }
三、链表中倒数第k个结点
题目链接：链表中倒数第k个结点_牛客题霸_牛客网
对于这道题目，与第二题十分相似，也是采用快慢指针的方式，不过不同的是，这里的快慢是距离的快慢，而上一道题是速度的快慢。
这道题目的关键就是，fast应该要先走k步，然后两者再一起走，当fast为空的时候，返回慢指针即可
如果fast先走k-1步，那么fast的下一个指针为空的时候，返回慢指针
注意如果链表为空，那么直接返回空即可，如果k大于链表长度，那么就直接返回空就可以，这就意味着，fast先走的时候，每走一步都要判断一下此时fast是否为空
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pListHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { if(pListHead==NULL) { return NULL; } // write code here struct ListNode* fast = pListHead; struct ListNode* slow = pListHead; while(k--) { if(fast!=NULL) fast=fast->next; else return NULL; } while(fast) { fast=fast->next; slow=slow->next; } return slow; }
四、反转链表
题目描述：力扣
解一：直接改变指向
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ struct ListNode* prev=NULL; struct ListNode* cur=head; while(cur!=NULL) { struct ListNode* next=cur->next; cur->next=prev; prev=cur; cur=next; } return prev; }
如上代码所示，这是最容易想到的方法，直接改变指向，我们先定义三个指针，prev，cur和next，然后使用循环依次改变指向即可
解二：头插法
这个的思路跟前面的尾插法类似， 我们可以定义一个新的链表newhead，然后将原来链表的头一个一个取出来进行头插即可
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newhead=NULL; struct ListNode* cur=head; while(cur!=NULL) { struct ListNode* next=cur->next; cur->next=newhead; newhead=cur; cur=next; } return newhead; }
五、合并两个有序链表
题目描述：力扣
解一：尾插法
这道题目也是比较适合尾插，如果第一个链表的数据小于第二个链表的数据，那么就尾插第一个，然后cur向后移动，反之也是一样的，代码如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode* cur1=list1; struct ListNode* cur2=list2; struct ListNode* newhead=NULL; struct ListNode* tail=NULL; while(cur1&&cur2) { if((cur1->val)<(cur2->val)) { if(newhead==NULL) { newhead=tail=list1; cur1=cur1->next; } else { tail->next=cur1; tail=cur1; cur1=cur1->next; } } else { if(newhead==NULL) { newhead=tail=list2; cur2=cur2->next; } else { tail->next=cur2; tail=cur2; cur2=cur2->next; } } } if(cur1==NULL) { tail->next=cur2; } else { tail->next=cur1; } return newhead; }
解二：哨兵位
我们可以先创建一个哨兵位，然后利用这个哨兵位去修改解法一的代码。可以一定程度上优化代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode* cur1=list1; struct ListNode* cur2=list2; struct ListNode* guard=NULL; struct ListNode* tail=NULL; guard=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); tail->next=NULL; while(cur1&&cur2) { if((cur1->val)<(cur2->val)) { tail->next=cur1; tail=cur1; cur1=cur1->next; } else { tail->next=cur2; tail=cur2; cur2=cur2->next; } } if(cur1==NULL) { tail->next=cur2; } else { tail->next=cur1; } struct ListNode* head=guard->next; free(guard); guard=NULL; return head; }
六、分割链表
题目链接：力扣
解一：尾插法（不带哨兵位）
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* partition(struct ListNode* head, int x){ struct ListNode* lesshead=NULL; struct ListNode* lesstail=NULL; struct ListNode* greaterhead=NULL; struct ListNode* greatertail=NULL; struct ListNode* cur=head; while(cur!=NULL) { if(cur->val<x) { //尾插到较小的链表 if(lesshead==NULL) { lesshead=lesstail=cur; cur=cur->next; } else { lesstail->next=cur; lesstail=cur; cur=cur->next; } } else { if(greaterhead==NULL) { greaterhead=greatertail=cur; cur=cur->next; } else { greatertail->next=cur; greatertail=cur; cur=cur->next; } } } if(lesshead==NULL) { return greaterhead; } if(greaterhead==NULL) { return lesshead; } lesstail->next=greaterhead; greatertail->next=NULL; return lesshead; }
对于这道题，依旧采取尾插法，既然要使用尾插法，那么势必需要构建两个新链表
题目要求是将所有小于x 的值全部放在前面，且不改变顺序
那么可以使用一个链表去管理小于x 的值。同样由于是尾插，需要使用头尾两个结点来管理
然后使用另外一个链表去管理大于等于x的值，也需要使用头尾两个结点去管理
由于是尾插，那么势必涉及到链表为空，这里的链表为空状态比较复杂。如果采用哨兵位的话，确实可以避免分情况讨论了。但是这里我们选择迎难而上，不采用哨兵位的解法
既然不采用哨兵位了，那么我们现在来分析这道题，首先是定义四个结点指针，然后我们去遍历原来的链表，如果小于x，尾插到较小链表，这里要注意，如果链表为空，需要分情况讨论。
如果大于等于x，尾插到较大链表，这里也要注意，如果链表为空，也需要分情况讨论
当尾插全部完成以后。
我们还需要进行分情况讨论，如果较小链表为空，那么直接返回较大链表即可，如果较大链表为空，返回较小链表即可。
然后我们链接较小链表和较大链表，最后要注意较大链表的尾部一定要置空，否则由于尾插可能会导致出现环。代码如上所示
解二：尾插法（带哨兵位）
前面我们已经知道了不带哨兵位的方法，我们发现，分情况讨论特别繁琐。对于尾插法，如果使用哨兵位，就可以直接无视掉所有的分情况讨论。而大体思路却不会变化太多，下面是代码。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* partition(struct ListNode* head, int x){ struct ListNode* lessGuard=NULL; struct ListNode* lesstail=NULL; struct ListNode* greaterGuard=NULL; struct ListNode* greatertail=NULL; lessGuard=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode)); greaterGuard=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode)); greatertail->next=NULL; lesstail->next=NULL; struct ListNode* cur=head; while(cur!=NULL) { if(cur->val<x) { lesstail->next=cur; lesstail=cur; cur=cur->next; } else { greatertail->next=cur; greatertail=cur; cur=cur->next; } } lesstail->next=greaterGuard->next; greatertail->next=NULL; head=lessGuard->next; free(lessGuard); free(greaterGuard); lessGuard=greaterGuard=NULL; return head; }
这里我们有一点需要特别注意，一定要让greatertail->next置为空，否则会陷入死循环，这也是使用哨兵位就需要做的一些细节，一旦使用哨兵位，一定要注意一些细节
本小节内容就到这里了，欲知后事请看下节
如果对你有帮助的话，一定要点赞加收藏哦！！！
