老铁们,现在开讲啦!!
下面是本期的OJ试题 :>
1.给定一个带有头结点head的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
现列图式样所示 :>
上图只有一个中间结点,因此返回后输出为 :> [3, 4, 5]
下面是有两个结点的情况,要返回第二个结点 :
上述第二种情况,输出的结果为 :> [4, 5, 6]
因此,我们要如何实现上述的情景,这是当下的重要环节,没有之一!!
这里,介绍一下,快慢指针的做法 :
由上图所示的代码显示 :>
慢指针“slow”每次循环一次,只向前走一步
快指针“fast”每次循环一次,确实向前走两步!!
下图所示,是即将终止运行过程的图示(意即最后一步)
因此fast ->next 就为NULL 了,此时终止循环,返回 slow慢指针,就可以得到想要的结果了!!
显然结点个数还有偶数个的情况 :>
此时上述的流程图,真实反映了,偶数结点个数的情况!!
当 fast为NULL时,就会终止循环,返回的仍旧是 slow慢指针,就可以得到我们想要的结果了!!
另外,强烈推荐,一定要亲手画上一遍流程图,你会发现一切的逻辑都是So easy !!
2.输入一个链表,输出该链表中的倒数第K个结点!!
上一道OJ题,讲述了,快慢指针的运用!!本题,仍然是用它,不过方式方法却有了变化!!
变得更加灵活了!!
现附上所需实现代码 :>
测试环节 :
实现环节:
调试环节:
请看箭头所指,地址是相同的!!意味着代码逻辑正确,预期结果符合要求!!
本题OJ题,继续运用了快慢指针的思想,是不是很强大!!
好了,老铁们!!本期就到这里了!!感谢阅读!!希望能对你们有所帮助!!