网站建设与管理下拉列表框百度关键词搜索指数
目录
一、移除链表元素
二、链表的中间结点
三、链表中倒数第k个结点
四、反转链表
五、合并两个有序链表
六、分割链表
一、移除链表元素
题目描述：力扣
法一：直接循环依次判断
对于这个题目，我们最容易想到的一种思路就是，直接遍历链表，当链表的值是需要删除的时候，直接删除即可，然后改变连接关系即可
代码如下
/*** 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 herestruct ListNode* fast = pListHead;struct ListNode* slow = pListHead;while(k--){if(fast!=NULL)fast=fast->next;elsereturn 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置为空，否则会陷入死循环，这也是使用哨兵位就需要做的一些细节，一旦使用哨兵位，一定要注意一些细节
本小节内容就到这里了，欲知后事请看下节
如果对你有帮助的话，一定要点赞加收藏哦！！！