链表倒数第n个节点

题目

找到单链表倒数第n个节点,保证链表中节点的最少数量为n。http://www.lintcode.com/zh-cn/problem/nth-to-last-node-in-list/

分析

只要知道了整个链表的长度,就可以计算出来倒数第n个节点是正数第几个。

当然,还可以通过一个长度为n的队列,一次遍历链表,取出队列第一个元素就是倒数第n个节点。

代码




public class Solution {
    
    int size(ListNode head){
        int i=0;
        while(head != null){
            i++;
            head = head.next;
        }
        return i;
    }
    /*
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: Nth to last node of a singly linked list. 
     */
    public ListNode nthToLast(ListNode head, int n) {
        // write your code here
        int length = size(head);
        int pos = length - n;
        for(int i=0; i < pos; i++){
            head = head.next;
        }
        return head;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.