分享
2020年07月16日:如何获得一个链表的倒数第n个元素?
福大大架构师每日一题 · · 1508 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
福哥答案2020年07月16日:
1.快慢指针。快指针先走n步,然后快慢指针同时走,直到快指针走到尾。
2.两次遍历。第一次遍历获取链表长度,然后计算出序号,然后遍历获取序号下的元素。
3.数组保存。遍历一次保存到数组,然后计算序号,这样就能获取到元素。
4.栈保存。遍历一次链表,遍历的过程中将元素放到一个栈当中,遍历完毕之后再将元素从栈中弹出,弹出的第n个元素就是倒数第n个元素。
最好的方式是第1种方式。但是对于大公司的面试,可不仅仅是解题,还会让你说出好几种方法,面试才能过关。
代码用golang编写,采用第1种方式,代码在leetcode里测试,题目是【面试题 02.02. 返回倒数第 k 个节点】,代码如下:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func kthToLast(head *ListNode, k int) int {
//快慢指针
fast := head
slow := head
//快指针先走k步
for k > 0 {
fast = fast.Next
k--
}
//快慢指针走剩下的,直到快指针走到尾
for fast != nil {
slow = slow.Next
fast = fast.Next
}
//慢指针就是所求的值
return slow.Val
}
执行结果如下:
image.png
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1508 次点击
上一篇:golang 分析调试高阶技巧
下一篇:【golang】常用文件操作
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
福哥答案2020年07月16日:
1.快慢指针。快指针先走n步,然后快慢指针同时走,直到快指针走到尾。
2.两次遍历。第一次遍历获取链表长度,然后计算出序号,然后遍历获取序号下的元素。
3.数组保存。遍历一次保存到数组,然后计算序号,这样就能获取到元素。
4.栈保存。遍历一次链表,遍历的过程中将元素放到一个栈当中,遍历完毕之后再将元素从栈中弹出,弹出的第n个元素就是倒数第n个元素。
最好的方式是第1种方式。但是对于大公司的面试,可不仅仅是解题,还会让你说出好几种方法,面试才能过关。
代码用golang编写,采用第1种方式,代码在leetcode里测试,题目是【面试题 02.02. 返回倒数第 k 个节点】,代码如下:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func kthToLast(head *ListNode, k int) int {
//快慢指针
fast := head
slow := head
//快指针先走k步
for k > 0 {
fast = fast.Next
k--
}
//快慢指针走剩下的,直到快指针走到尾
for fast != nil {
slow = slow.Next
fast = fast.Next
}
//慢指针就是所求的值
return slow.Val
}
执行结果如下:
image.png