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

定義兩個(gè)指針，p1,p2.
p1 從頭指向尾，p2指向我們需要?jiǎng)h除元素的前一個(gè)元素。p1 先出發(fā)，一直到領(lǐng)先p2 n 個(gè)元素的時(shí)候，這個(gè)時(shí)候p2出發(fā)，等到p1到達(dá)最后一個(gè)位置的時(shí)候，p2的位置就是我們要?jiǎng)h除元素的前一個(gè)元素。

注意

p1的初始位置就是head,p2的初始位置則是head的前一個(gè)元素，head前一個(gè)元素？對，這個(gè)時(shí)候需要自己定義一個(gè)頭結(jié)點(diǎn)之前的一個(gè)node,這樣會(huì)帶來一些方便（還有一些麻煩）

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是刪不掉真正的數(shù)據(jù)的，刪除的只是這個(gè)數(shù)據(jù)的某一個(gè)引用。所以如果要?jiǎng)h除的元素恰恰是head的話（比如說([1],1)這個(gè)輸入，不加mark1 , mark2的代碼的話返回的結(jié)果就是1,但是我們需要的肯定是[]）解決的方法是我們可以進(jìn)行一下判斷，如果p2(待刪除元素的上一個(gè)元素).next == head，那么就設(shè)置head = head.next，因?yàn)樽詈蠓祷氐囊檬莌ead，所以對del tmp對head并沒有什么影響。
這里注意python的del與C++ 的delete完全不一樣，delete是刪除內(nèi)存，del只是將一個(gè)元素的引用清理掉，怎么進(jìn)行內(nèi)存清理時(shí)Python解釋器的事情。

Performance

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