Leetcode 19 Remove Nth Node From

Question

Given a linked list, remove the nth node from the end of list and return its head.

 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.

Notes:
Given n will always be valid.
Try to do this in one pass.

Thinking

定义两个指针，p1,p2.
p1 从头指向尾，p2指向我们需要删除元素的前一个元素。p1 先出发，一直到领先p2 n 个元素的时候，这个时候p2出发，等到p1到达最后一个位置的时候，p2的位置就是我们要删除元素的前一个元素。

注意

p1的初始位置就是head,p2的初始位置则是head的前一个元素，head前一个元素？对，这个时候需要自己定义一个头结点之前的一个node,这样会带来一些方便（还有一些麻烦）

Codes

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        p1 = head
        p2 = ListNode('#')
        p2.next = head
        cnt = 1
        while p1.next is not None:
            p1 = p1.next
            if cnt >= n:
                p2 = p2.next
            cnt += 1
        # now p2 is the pre-node of the node to delete
        tmp = p2.next
        if tmp is None:
            pass
        else:
            p2.next = tmp.next
            if tmp == head:   # mark1
                head = head.next  # mark2
            del tmp
        return head

Key Points

在python 中del是删不掉真正的数据的，删除的只是这个数据的某一个引用。所以如果要删除的元素恰恰是head的话（比如说([1],1)这个输入，不加mark1 , mark2的代码的话返回的结果就是1,但是我们需要的肯定是[]）解决的方法是我们可以进行一下判断，如果p2(待删除元素的上一个元素).next == head，那么就设置head = head.next，因为最后返回的引用是head，所以对del tmp对head并没有什么影响。
这里注意python的del与C++ 的delete完全不一样，delete是删除内存，del只是将一个元素的引用清理掉，怎么进行内存清理时Python解释器的事情。

Performance

好像每一次都不一样？python 大法好....