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.

Given a List 3->2->1->5->null and n = 2, return node whose value is 1.

http://www.lintcode.com/en/problem/nth-to-last-node-in-list/

Discussion

常规思路就不说了。这里主要思路就是使用两个指针，先让前面的指针走到正向第n个结点, 然后两个指针同时走，这样第一个指针指向链表尾部的NULL的时候，第二个指针就来到了倒数 第n个节点了。快慢指针的思想

需要注意的是n可能大于整个链表的长度了，也就是还没移动n次呢就到队尾了。根据一个具体的例子coding。

Solution

class Solution {
public:
    /**
     * @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) {
        // write your code here
        if(n<=0 || head == NULL) return NULL;
        int len=0;
        ListNode dummy(-1);
        dummy.next = head;
        ListNode *first = &dummy;
        ListNode *second = &dummy;
        int i = 0;
        for(i=0; i<n; i++) {
            if(first->next != NULL)
                first = first->next;
            else 
                break;
        }
       if(i != n)
           return NULL;
        while(first != NULL) {
            first = first->next;
            second = second->next;
        }
        return second;
    }
};