前言
在上一期中我们介绍了单链表，也对单链表的实现进行具体的了解，接下来我们开始单链表的练习，对单链表更深层的理解，让小伙伴们灵活的使用单链表，话不多说，开造~
一、移除链表元素
💭方法一：
我们使用两个指针遍历数组，遇到与 val 相同的结点时，就删除这个节点。我们在思考问题时要想全面，当要删除头节点时，常规方法就无法实现，对于删除头节点要做单独处理。
常规删除：
头节点删除：
思路：(1)首先给出判断cur是否是空的，不是空的之后，判断是否有val，有的话就判断是否在头部，是的话一种情况，不是的话，又是一种情况。（2）第一种情况，题意所给出的情况；第二种情况，中间连续个value（前两种可以合并）；第三种情况，一开始就出现6或者连续个6；第四种情况：空的
struct ListNode* removeElements(struct ListNode* head, int val) { if (head == NULL) return head; struct ListNode* prev = NULL, * cur = head; while (cur) { struct ListNode* Next = cur->next; if (cur->val == val) { if (prev == NULL) { head = Next; cur = Next; } else { prev->next = Next; free(cur); cur = Next; } } else { prev = cur; cur = Next; } } return head; }
💭方法二：
我们通过遍历，把节点的数据域不等于val的节点尾接到新的链表中。我们要考虑第一个节点是不是要删除的。最后一个节点的指针域置空要放在循环结束后，判断tail是否为空指针。
truct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newnode=NULL; struct ListNode* cur=head,*tail=newnode; while(cur) { if(cur->val!=val) { if(tail==NULL) { newnode=cur; tail=newnode; } else { tail->next=cur; tail=tail->next; } cur=cur->next; } else { struct ListNode* del=cur; cur=cur->next; free(del); } } if(tail) { tail->next=NULL; } return newnode; }
二、寻找链表中间结点
我们可以定义两个指针，快指针一次走两步，慢指针一次走一步，当快指针走到结尾时，慢指针正好走了一半，这样我们就可以找到中间节点。
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow=head,*fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } return slow; }
三、输出链表倒数第k个结点
我们可以参考上一题的方法，同样定义快慢指针，先让快指针走k步，然后再同时走，走到fast为空指针就找了倒数第k个节点。有可能链表没有k个节点，所以我们要加入判断。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* slow=pListHead,*fast=pListHead; while(k--) { if(fast==NULL) { return NULL; } fast=fast->next; } while(fast) { slow=slow->next; fast=fast->next; } return slow; }
四、反转单链表
💭方法一：
我们定义三个指针n1,n2,n3，来改变节点链接的顺序。将头节点变为尾节点，当n2为空指针时，n1就为链表的头节点，只需返回n1就可以。两个指针倒方向，一个指针保持下一个。
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* n1=NULL,*n2=head,*n3=NULL; if(head==NULL) return head; while(n2) { n3=n2->next; n2->next=n1; n1=n2; n2=n3; } return n1; }
💭方法二：
将链表的节点一个一个拿下来，进行头插。这里要注意赋值的顺序。
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head; struct ListNode* newnode=NULL; while(cur) { //保存节点 struct ListNode* next=cur->next; //头插 cur->next=newnode; newnode=cur; cur=next; } return newnode; }
五、合并两个有序链表
思路：每次取小的节点尾插到新的节点
注意：其中一个为空的情况要注意
💭代码一：（不带头）
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) return list2; if(list2==NULL) return list1; struct ListNode* head=NULL; struct ListNode* tail=NULL; while(list1&&list2) { if((list1->val) < (list2->val)) { if(tail==NULL) { head=list1; tail=list1; } else { tail->next=list1; tail=list1; } list1=list1->next; } else { if(tail==NULL) { head=list2; tail=list2; } else { tail->next=list2; tail=list2; } list2=list2->next; } } if(list1) tail->next=list1; if(list2) tail->next=list2; return head; }
有头单链表：head->next指的是第一个节点的地址（带头，相当于开头多了一个节点，但是节点里面的val不确定，next指向下一个节点）； 无头单链表：head指的是第一个节点的地址； OJ题默认不带头
💭代码二：（带头）
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));//创建一个头 struct ListNode* tail = head; head->next = NULL;//就是含有值的节点的第一个 while (list1 && list2) { struct ListNode* next1 = list1->next; struct ListNode* next2 = list2->next; if ((list1->val) < (list2->val)) { tail->next = list1; tail = list1; list1 = next1; } else { tail->next = list2; tail = list2; list2 = next2; } } if (list1 != NULL) { tail->next = list1; } if (list2 != NULL) { tail->next = list2; } struct ListNode* list = head->next; free(head); return list; }
思路：每次取小的节点尾插到新的节点
注意：mallloc的一个地址，到最后要进行释放。
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~
