Code Ganker: Remove Nth Node From End of List -- LeetCode

2014年2月23日星期日

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,大家还是尽量考虑,因为题目比较简单,更多的只能去关注这些问题。

没有评论:

发表评论