一.【Leetcode203】移除链表元素
1.链接
2.题目再现
A.双指针法
1.创建一个指针 cur=head 和一个指针 pre=NULL；
2.用cur->val 与 val 比较,如果不相等则把 cur 赋给 pre 使cur 指向下一个节点，即
cur=cur->next；
3.如果相等则使 pre 的 next 指向 cur 的 next ，即：
pre->next=cur->next ，然后再 free 掉 cur ,最后再使 cur 等于 pre 的 next，注意在进行这些步骤之前要判断 pre 是否为空 ，若为空即为头删；
演示：
双指针
代码：
1. struct ListNode* removeElements(struct ListNode* head, int val) 2. { 3. struct ListNode*pre=NULL; 4. struct ListNode*cur=head; 5. while(cur) 6. { 7. if(cur->val!=val) 8. { 9. pre=cur; 10. cur=cur->next; 11. } 12. else 13. { 14. if(pre==NULL) 15. { 16. head=cur->next; 17. free(cur); 18. cur=head; 19. } 20. else 21. { 22. pre->next=cur->next; 23. cur=pre->next; 24. } 25. } 26. } 27. return head; 28. }
B.类尾删法
1.创建一个新的指针newhead ，同时为了省去找尾的麻烦，我们可以定义一个尾指针 tail 来保存尾节点；
2.再创建一个指针 cur =head ,用来遍历链表；
3.如果 cur->val != val ，则尾插 ，注意要判断 tail 是否为空 ，类似于单链表的尾插那部分，如果不理解的话，可查看文章 ：单链表的增删查改；
4.如果 cur->val ==val，则 cur=cur->next ；
5.最后要将尾节点置空。
演示：
类尾插
代码：
1. struct ListNode* removeElements(struct ListNode* head, int val) 2. { 3. struct ListNode *newhead=NULL; 4. struct ListNode*tail=NULL; 5. struct ListNode*cur=head; 6. while(cur) 7. { 8. if(cur->val!=val) 9. { 10. if(tail==NULL) 11. { 12. newhead=tail=cur; 13. } 14. else 15. { 16. tail->next=cur; 17. tail=tail->next; 18. } 19. cur=cur->next; 20. } 21. else 22. { 23. cur=cur->next; 24. } 25. } 26. if(tail) 27. { 28. tail->next=NULL; 29. } 30. return newhead; 31. }
C.哨兵位
1.malloc 一个哨兵位节点 dummyhead，使其 next 指向 head ；
2.再定义一个节点 tmp = dummyhead ，用这个遍历链表；
3.注意因为 tmp ->next 才是 head ，所以 while 里要写 tmp->next !=NULL
演示：
移除链表元素 哨兵位法动态演示
代码：
1. struct ListNode* removeElements(struct ListNode* head, int val) 2. { 3. struct ListNode*dummyhead=(struct ListNode*)malloc(sizeof(struct ListNode)); 4. dummyhead->next=head; 5. struct ListNode*tmp=dummyhead; 6. while(tmp->next!=NULL) 7. { 8. if(tmp->next->val==val) 9. { 10. tmp->next=tmp->next->next; 11. } 12. else 13. { 14. tmp=tmp->next; 15. } 16. } 17. return dummyhead->next; 18. }
二.【Leetcode876】链表的中间节点
1.链接：链表的中间节点
2.题目再现
3.解法：快慢指针
1.定义一个快指针 fast 和一个慢指针 slow 都初始化为 head;
2.遍历链表，快指针一次走2步，慢指针一次走1步 ；
3.注意：因为链表的长度可能是单数也可能是双数，所以当我们已 fast 是否为NULL 作为循环控制条件的话，要在 fast 走2步前判断 fast->next 是否为空；
4.最后慢指针就是中间节点。
演示：
链表中间节点 快慢指针动态演示
代码：
1. struct ListNode* middleNode(struct ListNode* head) 2. { 3. struct ListNode*slow=head; 4. struct ListNode*fast=head; 5. while(fast) 6. { 7. if(fast->next==NULL) //注意判断 8. { 9. break; 10. } 11. else 12. { 13. fast=fast->next->next; //fast 走2步 14. } 15. slow=slow->next; //slow 走1步 16. } 17. return slow; //返回慢指针 18. }
三.链表中倒数第k个节点
1.链接：链表中倒数第k个节点
2.题目再现
3.解法 ：快慢指针
1.定义一个快指针 fast 和一个慢指针 slow 都初始化为 head;
2.因为倒数第k个节点和尾节点的差为 k-1 ，所以我们先让快指针先走 k-1 步；
或者因为尾节点所指向的NULL 和倒数第k个节点相差k，也可以先让快指针走k步；
这个时候慢指针不动；
3.快指针走完后，快指针和慢指针依次走，每次只走1步；
注意，如果是k-1，那么遍历结束的条件是fast->next 是否为空 ，如果是k，那么遍历结束的条件是fast 是否为空；
4.返回慢指针。
演示：
链表倒数第K个节点 快慢指针动态演示
代码：
1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 2. { 3. if(pListHead==NULL) 4. { 5. return NULL; 6. } 7. struct ListNode*slow=pListHead; 8. struct ListNode*fast=pListHead; 9. while(k--) //这里以先走k步为例 10. { 11. if(fast==NULL) 12. { 13. return NULL; 14. } 15. fast=fast->next; 16. } 17. while(fast) 18. { 19. slow=slow->next; 20. fast=fast->next; 21. } 22. return slow; 23. }
😽本篇文章到此就结束了，若有错误或是建议，欢迎小伙伴们指出；😻
😍请多多支持博主哦~🥰
🤩谢谢你的阅读~😃
