#### 19.Remove Nth Node From End of List
Given a linked list, remove the *n*th node from the end of list and return its head.
For example,
```
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
```
**Note:**
Given *n* will always be valid.
Try to do this in one pass.
#### 思路
删除单链表中节点 `node`,需要找到其前驱节点 `preNode`,再执行删除: `preNode.Next = preNode.Next.Next`
题中删除倒数第 n 个节点,只需找到倒数第 n+1 个节点即可
##### 思路1
第一次遍历链表算出节点总数 N,计算倒数第 n+1 个节点的位置,第二次遍历找到这个前驱节点,执行删除。
时间复杂度 O(N):遍历链表的总时间是 `N + N - n`
空间复杂度 O(1):运算临时占用的空间大小固定
##### 思路2
设置两个指针 cur、pre 初始位置如下,间隔 n 个节点,遍历链表当 cur 达到尾部时,pre 正是倒数第 n+1 个节点 ![](https://github.com/wuYinBest/leetcode/blob/master/linked_list/19.remove_nth_node_from_end_of_list/process.png?raw=true)
时间复杂度 O(N):比起思路一要少一次遍历,总时间为 `N`
空间复杂度 O(1)
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
用来记录我们刷LeetCode题目时候的心酸历史。我们保证,这些代码一定通过了当时LeetCode的测试,虽然后续可能因为LeetCode测试条件的改变导致某些解题无法通过,但我们会实时的跟进。 编程语言使用Golang,代码风格上面并没有强制的采用什么编码规范,毕竟是算法解题,只需要代码清晰易懂就可以了。 鉴于个人精力时间有限,可能并不会完全最优解,请多多见谅。
资源推荐
资源详情
资源评论
收起资源包目录
leetcode-master-Golang.rar (19个子文件)
leetcode-master-Golang
linked_list
23.merge_k_sorted_lists
merge_k_sorted_lists_test.go 458B
merge_k_sorted_lists.go 2KB
README.md 1KB
devide.png 13KB
21.merge_two_sorted_lists
merge_two_sorted_lists_test.go 211B
README.md 384B
merge_two_sorted_lists.go 616B
19.remove_nth_node_from_end_of_list
remove_nth_node_from_end_of_list.go 1KB
remove_nth_node_from_end_of_list_test.go 432B
README.md 1KB
process.png 6KB
2.add_two_numbers
add_two_numbers_test.go 558B
add_two_numbers.go 1KB
README.md 696B
24.swap_nodes_in_pairs
swap_nodes_in_pairs.go 511B
README.md 1KB
swap.png 9KB
swap_nodes_in_pairs_test.go 269B
README.md 125B
共 19 条
- 1
资源评论
- zhuwei138142019-07-29很有用 算法写的很好
- 鱼鱼he胖胖2019-07-29很有用,不过有点少,只有5道题,不过让我了解了一些golang的规范用法,算法也很好,写的很好,赞
- syswin_2018-09-27很有用,不过有点少,只有5道题,不过让我了解了一些golang的规范用法,算法也很好,写的很好,赞
- BBOYIORI2019-06-18很有用,不过有点少,只有5道题,不过让我了解了一些golang的规范用法,算法也很好,写的很好,赞
April94
- 粉丝: 1
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- STM32单片机FPGA毕设电路原理论文报告嵌入式系统工程专业单片机课程教学改革与实践
- STM32单片机FPGA毕设电路原理论文报告嵌入式单片机与PC机组合应用
- STM32单片机FPGA毕设电路原理论文报告嵌入式单片机PPP协议的应用研究
- STM32单片机FPGA毕设电路原理论文报告嵌入式USB主机接口在温室环境监控中的应用研究
- STM32单片机FPGA毕设电路原理论文报告嵌入式usb数据采集系统
- 10个LED.pdsprj
- BaiduyunSpider-master.zip
- STM32单片机FPGA毕设电路原理论文报告嵌入式TCPIP协议单片机在网络通信中的应用
- localsend文件传输工具mac端
- STM32单片机FPGA毕设电路原理论文报告嵌入式linux下基于单片机的矩阵键盘与ARM的串行通信
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功