Remove Nth Node From End of List
Problem
- source(lintcode): https://www.lintcode.com/problem/remove-nth-node-from-end-of-list/
- source(leetcode): https://leetcode.com/problems/remove-nth-node-from-end-of-list/ ### Description
Given a linked list, remove the nth node from the end of list and return its head.
Notice
The minimum number of nodes in list is n.
Example
Given linked list:
1->2->3->4->5->null
, and n =2
.
After removing the second node from the end, the linked list becomes 1->2->3->5->null
.
Challenge
Can you do it without getting the length of the linked list?
题解
简单题,使用快慢指针解决此题,需要注意最后删除的是否为头节点。让快指针先走n
步,直至快指针走到终点,找到需要删除节点之前的一个节点,改变node->next
域即可。见基础数据结构部分的链表解析。
C++
1 | /** |
Java
1 | /** |
源码分析
引入dummy
节点后画个图分析下就能确定head
和preDel
的转移关系了。 注意 while 循环中和快慢指针初始化的关系,否则容易在顺序上错一。
复杂度分析
极限情况下遍历两遍链表,时间复杂度为 \[O(n)\].
Remove Nth Node From End of List