Remove Nth Node From End of List

最新更新的解法和思路：https://yanjia.me/zh/2018/11/...

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

代码

java

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;
    }
}

python

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        fast = dummy
        for i in range(0, n):
            fast = fast.next
        slow = dummy
        while(fast.next is not None):
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next