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;    }}