一.移除链表元素
- 本题oj链接如下:移除链表元素
其中关于题目的文字描述并不难理解,通过结合给的示例我们知道本题想要删除链表中所有等于val的值,返回把剩下节点连在一起的头节点。
下面提供改题目的解答思路以及代码实现
1.该题其实与我们之前讲的单链表的中间删除非常相似,只不过我们的中间删除是通过地址来找到需要删除的位置,而本题需要的找到节点中等于val的值删除,我们只需要让等于val的节点的前一个节点跳过值等于val的节点指向val下一个节点,最后再把等于val的节点free释放掉即可
struct ListNode* removeElements(struct ListNode* head, int val) { if(head == NULL)//链表中什么都没有 return NULL; struct ListNode* cur = head; struct ListNode* prev = NULL; while(cur) { //如果当前节点是需要删除的节点 if(cur->val == val) { //首先保存下一个节点 struct ListNode* next = cur->next; //如果删除的为头节点,更新头节点 //否则让当前节点的前趋节点链接next节点 if(prev == NULL) { head = cur->next; } else { prev->next = cur->next; } //释放当前节点,让cur指向next free(cur); cur = next; } else { //如果cur不是需要删除的节点,则更新prev,cur prev = cur; cur = cur->next; } } return head;//返回新头 }
二.反转链表
- 本题oj链接如下:反转链表
- 该题有两种思路,我们分别来介绍一下,并代码实现
- 1.链表中有一种插入方式叫头插,顾名思义就是在头部进行节点的插入,比如你在链表中依次头插 1 2 3 4 5,那么其实在链表中其实是反过来依次从头插的,也就是 5 4 3 2 1.这与我们这题想要我们实现的反转链表不就对上了吗?
struct ListNode* reverseList(struct ListNode* head){ //把原链表中的节点依次头插入新链表中 struct ListNode*newnode=NULL; struct ListNode*cur1=head; while(cur1) { //头插 struct ListNode*next=cur1->next; cur1->next=newnode; newnode=cur1; cur1=next; } return newnode; }
- 2.通过三个指针倒转该链表,我们假设此时有三个指针,其中n1指向head,n2指向n1的next,n3指向n2的next,此时逻辑图如图所示。
我们想要该链表反转,我们可以让链接两个节点的箭头转向,用c语言的话来说,就是让该节点的指针从指向下一个节点变为指向上一个节点,由于此时的1变为了新的尾,我们把1的next置空,如图`
- 当我们完成这一步后,下面我们需要把三个指针都往前走一步,让链表中未反转的节点也反转一下
- 我们的结束条件是什么呢?当我们的n1是最后一个节点时,说明我们链表中所有的节点都已经反转完成,此时是不是就可以停了?此时由于n2为的前一位,也就是n2为空时,n1就来到了我们的最后一位,因此我们可以把n2为空作为循环停止的条件
struct ListNode* reverseList(struct ListNode* head) { if(head == NULL || head->next == NULL)//说明此时只有一个节点或者没有节点,直接返回head即可 return head; struct ListNode* n1, *n2, *n3; n1 = head; n2 = n1->next; n3 = n2->next; n1->next = NULL; //中间节点不为空,继续修改指向 while(n2) { //中间节点指向反转 n2->next = n1; //更新三个连续的节点 n1 = n2; n2 = n3; if(n3)//防止n3越界,判断一下n3是否为空 n3 = n3->next; } //返回新的头 return n1; }
3.链表的中间结点
- oj链接如下:链表的中间结点
- 这个oj题同样有两种解法,我们还是来一种一种的分析
- 1.暴力求解法
- 题目要求的是找到链表的中间结点,那么我们首先可以先遍历一遍链表同时计数,以此达到记录链表中有多少结点的目标,之后我们在取计数的一半,让链表遍历一半,此时的结点就是我们的中间结点啦!
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*cur=head; struct ListNode*midcur=head; int size=0;//标记计数 while(cur) { size++; cur=cur->next; } int len=size/2;//取链表节点数的一半找到中间结点 while(len) { midcur=midcur->next; len--; } return midcur; }
- 第二种方法就比较巧妙了,我们现在来通过一个实际的例子来帮助大家理解。
- 某天,一个老和尚测试一个小和尚几个问题,并要求他在半炷香内回答出来,此时老和尚委托你来负责计时,但是由于寺庙里香不够了,只有一炷香供你计时,那么此时你应该怎么做呢?
- 答案是:从两头同时开始烧
- 这个实际的例子有没有带给你什么启发呢?我们同样是需要求链表的中间结点,也就是一半。
- 揭晓答案:使用快慢指针,快的一次走两步,慢的一次走一步,当快的走到尾时,慢的指针此时就在中间结点。
- 类比一下,此时快指针就是从两头烧,慢指针是从一头烧,当两头烧完时,就相当于一头烧烧完了半炷香!!
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*fast,*slow; fast=slow=head; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; } return slow; }
总结
- 今天的内容到这里就结束了,一次讲多了大家可能会贪多嚼不烂,所以暂时先介绍这三个典型的题,之后也会继续更新有关的其他题目。
- 切记如果你想要真正学好的话一定要自己动手试试哦,光看不自己写是永远学不会的!!
- 好了,如果你有任何疑问欢迎在评论区或者私信我提出,大家下次再见啦!