Remove Nth Node From End of List -- LeetCode

原题链接:http://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/

这道题是链表基本操作，主要问题就是如何得到链表的倒数第n个结点，应该是一个比较重要的routine，因为很多题目都要用这个subroutine。思路就是先用一个runner指针走n步，然后再来一个walker从头开始和runner同时向后走，当runner走到链表末尾的时候，walker指针即为倒数第n个结点。算法的时间复杂度是O(链表的长度)，空间复杂度是O(1)。代码如下：

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head == null)
        return null;
    int i=0;
    ListNode runner = head;
    while(runner!=null && i<n)
    {
        runner = runner.next;
        i++;
    }
    if(i<n)
        return head;
    if(runner == null)
        return head.next;
    ListNode walker = head;
    while(runner.next!=null)
    {
        walker = walker.next;
        runner = runner.next;
    }
    walker.next = walker.next.next;
    return head;
}

原题中假设n总是合法的，但是面试的时候最好不要做这种假设，或者至少要和面试官讨论一下。以上代码是如果n不合法，就直接返回链表头，也就是什么都不做。对于这种corner case，大家还是尽量考虑，因为题目比较简单，更多的只能去关注这些问题。