怎么做网站的301,深圳软件公司定制开发,上海市建设人才网站,教育类网站素材前言
学习了单链表#xff0c;我们就做一些题来巩固一下。还有就是解题方法不唯一#xff0c;我就只讲述为自己的方法。
目录
前言
1.移除链表元素 思路
代码
2.反转链表 思路 代码
3.链表的中间节点
思路 代码
总结 1.移除链表元素 思路
我们创建一个新的表…前言
学习了单链表我们就做一些题来巩固一下。还有就是解题方法不唯一我就只讲述为自己的方法。
目录
前言
1.移除链表元素 思路
代码
2.反转链表 思路 代码
3.链表的中间节点
思路 代码
总结 1.移除链表元素 思路
我们创建一个新的表来储存和val值不一样的节点。还可以在原表上删除和val值相同的节点。
这里我是新创建一个表来接受不等于val的节点。通过发现我们应该通过采取尾插的方式来储存新节点。如果循环里面就只要尾插会导致新表的头节点还是指向空指针导致输出错误。所以还要考虑新链表的头节点是否为空为空的话我们就新表的头节点和尾节点指向第一个节点。
完成以上步骤后会变成下面的样子最后一个节点还是指向要被删除的节点。导致输出结果还是含有被删除的值。所以我们要进行优化把新链表的尾节点指向NULL。最后返回头节点就可以了。 代码
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{ListNode*newhead,*newtail;//新链表的头尾节点newheadnewtailNULL;//遍历原链表ListNode* prevhead;while(prev){if(prev-val!val){if(newheadNULL){newheadnewtailprev;}else{newtail-nextprev;newtailnewtail-next;}}prevprev-next;}if(newtail)newtail-nextNULL;return newhead;
}
2.反转链表 思路
这里我的想法是反转链表指向来实现题目的效果定义3个节点分别用来存储NULL、第一个节点、第二个节点循环反转指向然后在循环让3个节点都向后移动其中n3、最先指向空其次是n2、最后是n1 n2-nextn1; n1n2; n2n3; n3n3-next; 这些就是向后移动的代码
我们最后要返回含val5的节点所以我们就让n2充当循环结束的条件但是这样写会出错因为n3最早变成空指针就可以对空指针进行解引用操作了。所以在前面加上一个if版判语句
ifn3n3n3-next; 最后返回n1就可以了。
如下图所示 代码
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{if(headNULL){return head;}ListNode* n1,* n2,* n3;n1NULL,n2head,n3n2-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}return n1;
}
3.链表的中间节点 思路
这里介绍一种新奇的方法那就是快慢指针。快指针移动两次慢指针移动一次。这里大家先知道怎么移动行了不用深究为什么。后面我会为大家解答的。
根据例1移动我们发现当fast移动到最后时slow就是我们要返回的值。我们又要把fast当作循环结束的条件。所以我们就可以想到fast-next 指针为空指针时结束循环。
根据例2移动我们可以等到循环结束的条件为fast为空指针时为循环结束条件。
我们把他们结合起来当作循环条件这样就万无一失了。返回慢指针slow 代码
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{ListNode* slowhead;ListNode* fasthead;while(fast fast-next){slowslow-next;fastfast-next-next;}return slow;
} 总结
做这种链表的问题最好就是画图理清思路然后再写代码。后还会为大家讲解单链表经典算法题 2。会持续更新的哦
