LintCode - 链表倒数第n个节点（普通）

版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：容易

要求：

找到单链表倒数第n个节点，保证链表中节点的最少数量为n

样例

给出链表** 3->2->1->5->null**和n = 2，返回倒数第二个节点的值1.

思路：
先翻转，再计算

/**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: Nth to last node of a singly linked list. 
     */
    ListNode nthToLast(ListNode head, int n) {
        if(head == null){
            return null;
        }
        
        head = reverse(head);
        int index = 1;
        while(head.next != null){
            if(index++ == n){
                break;
            }
            head = head.next;
        }
        return head;
    }
    
    /**
     * 原地翻转
     */
    private ListNode reverse(ListNode head){
        ListNode prev = null;
        while(head != null){
            ListNode tmp = head.next;
            head.next = prev;
            prev = head;
            head = tmp;
        }
        return prev;
    }

思路：
双指针，第一个指针先走n个，然后第一个指针和第二个指针同时往右遍历，当第一个指针为null时，第二个指针就为倒数第n个元素

/**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: Nth to last node of a singly linked list. 
     */
    ListNode nthToLast(ListNode head, int n) {
        if(head == null){
            return null;
        }
        
        ListNode dummy = head;

        for(int i = 0; i < n; i++){
            if(head == null){
                return null;
            }
            head = head.next;
        }
        
        ListNode pre = dummy;
        while(head != null){
            head = head.next;
            pre = pre.next;
        }
        
        return pre;
    }