Remove Nth Node From End of List

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.

迭代法

复杂度

时间 O(N) 空间 O(1)

思路

典型的快慢指针。先用快指针向前走n步，这样快指针就领先慢指针n步了，然后快慢指针一起走，当快指针到尽头时，慢指针就是倒数第n个。不过如果要删除这个节点，我们要知道的是该节点的前面一个节点。另外，如果要删的是头节点，也比较难处理。这里使用一个dummy头节点，放在本来的head之前，这样我们的慢指针从dummy开始遍历，当快指针为空是，慢指针正好是倒数第n个的前一个节点。最后返回的时候，返回dummy的下一个。

注意

因为有可能删除头节点，我们需要一个dummyhead

代码

public class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) {        ListNode fast = head;        ListNode dummy = new ListNode(0);        dummy.next = head;        // 快指针先走n步        for(int i = 0; i < n; i++){fast = fast.next;        }        // 从dummy开始慢指针和快指针一起走        ListNode curr = dummy;        while(fast != null){fast = fast.next;curr = curr.next;        }        // 删除当前的下一个节点        curr.next = curr.next.next;        return dummy.next;    }}