Leetcode - Remove Nth Node From End of List

Remove Nth Node From End of List Total Accepted: 63354 Total Submissions: 234837 My Submissions Question Solution
Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
[分析] 快慢指针思路。两指针初始均指向head，快指针尽量先走 n 步：
1）若快指针超过了最后一个节点，即为null：
a)若此时已走过n步，说明共有 n 个节点，需要删除第一个节点；
b)若此时尚未走完n步，说明链表长度小于n，无需删除任何节点
2）若快指针走完n步且没有超过最后一个节点，说明链表长度大于n，两指针开始同步前进，
快指针走到最后一个节点时，慢指针的下一个节点即为倒数第 n 个节点。

这题虽然为简单题，可是我并不能很快地做到bug free。

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0) return head;
        ListNode slow = head, fast = head;
        int i = 0;
        while(i < n && fast != null) {
            fast = fast.next;
            i++;
        }
        if (fast == null) return i < n ? head : head.next;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

评论

1 楼 qb_2008 2015-07-29  

用测试用例带入一下就好了