脚本宝典收集整理的这篇文章主要介绍了[Lintcode] Nth to Last Node in List 链表倒数第N个节点,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
Nth to Last Node in List
Find the nth to last element of a singly linked list.
The minimum number of nodes in list is n.
递归法
复杂度
时间 O(N) 空间 O(N)
思路
当递归到链表尾部时返回,每次返回时长度加1,一旦长度为N时记录下该节点。
双指针法
复杂度
时间 O(N) 空间 O(1)
思路
用两个指针,快指针先走N步,然后快慢指针同时开始走,保持N的距离,这样当快指针到达末尾时,慢指针就是倒数第N个。
代码
public class Solution {
ListNode nthToLast(ListNode head, int n) {
// write your code here
ListNode slow = head;
ListNode fast = head;
while(n-- > 0){
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
以上是脚本宝典为你收集整理的[Lintcode] Nth to Last Node in List 链表倒数第N个节点全部内容,希望文章能够帮你解决[Lintcode] Nth to Last Node in List 链表倒数第N个节点所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。