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 先出發(fā)，一直到領(lǐng)先p2 n 個元素的時候踩娘，這個時候p2出發(fā)，等到p1到達(dá)最后一個位置的時候喉祭，p2的位置就是我們要刪除元素的前一個元素养渴。
注意
p1的初始位置就是head,p2的初始位置則是head的前一個元素，head前一個元素泛烙？對理卑，這個時候需要自己定義一個頭結(jié)點之前的一個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是刪不掉真正的數(shù)據(jù)的，刪除的只是這個數(shù)據(jù)的某一個引用胶惰。所以如果要刪除的元素恰恰是head的話（比如說([1],1)這個輸入傻工，不加mark1 , mark2的代碼的話返回的結(jié)果就是1,但是我們需要的肯定是[]）解決的方法是我們可以進行一下判斷，如果p2(待刪除元素的上一個元素).next == head孵滞，那么就設(shè)置head = head.next中捆，因為最后返回的引用是head，所以對del tmp對head并沒有什么影響坊饶。
這里注意python的del與C++ 的delete完全不一樣泄伪，delete是刪除內(nèi)存，del只是將一個元素的引用清理掉匿级，怎么進行內(nèi)存清理時Python解釋器的事情蟋滴。
Performance
好像每一次都不一樣染厅？python 大法好....
