題目
給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點定拟，并且返回鏈表的頭結(jié)點环疼。
示例
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個節(jié)點后设江，鏈表變?yōu)?1->2->3->5.
說明：給定的 n 保證是有效的。
進階：你能嘗試使用一趟掃描實現(xiàn)嗎似袁？
解答
方案1：走兩趟
- 首先從頭到尾遍歷鏈表洞辣，統(tǒng)計輸入鏈表的長度list_len；
- 計算要刪除的節(jié)點位置昙衅，處理特殊情況扬霜，如輸入節(jié)點為空，要刪除的節(jié)點位置為0或負數(shù)等而涉；
- 把刪除倒數(shù)第N個節(jié)點轉(zhuǎn)變成刪除正數(shù)第list_len-N個節(jié)點的問題著瓶，從頭到尾遍歷鏈表，并刪除指定位置元素啼县；
我們這里刪除鏈表使用語句node.next = node.next.next即可刪除原先node.next位置的元素蟹但，代碼如下：
class Solution:
def removeNthFromEnd(self, head, n):
"""
解決思路：走兩趟
:param head:
:param n:
:return:
"""
def get_len(head): # 獲取一個鏈表的長度
n = 0
while head:
n += 1
head = head.next
return n
list_len = get_len(head)
if list_len == 0: # 輸入是個空鏈表
return
node_to_delete = list_len - n # 要刪除的節(jié)點的位置
if node_to_delete == 0:
return head.next
elif node_to_delete < 0:
return head
else:
# 將倒數(shù)第n個轉(zhuǎn)換為正數(shù)第cur_len - n個。
i = 0
cur_node = head
while cur_node:
if i == node_to_delete - 1: # 遇到了要刪除的結(jié)點的前一個結(jié)點
cur_node.next = cur_node.next.next # 刪除要刪除的結(jié)點
else:
cur_node = cur_node.next # 當(dāng)前指針后移
i += 1
return head # 返回鏈表頭結(jié)點
執(zhí)行用時 : 56 ms, 在Remove Nth Node From End of List的Python3提交中擊敗了80.63% 的用戶
內(nèi)存消耗 : 13 MB, 在Remove Nth Node From End of List的Python3提交中擊敗了93.66% 的用戶
（其實這個性能波動有時挺大）
方案2：快慢指針
我們定義兩個指針谭羔，快指針和慢指針华糖，讓快指針先于慢指針走N步，然后兩指針同步向后走瘟裸，當(dāng)快指針遍歷到鏈表末尾時客叉，刪除慢指針后的元素即可。
class Solution:
def removeNthFromEnd(self, head, n):
"""
解決思路：雙指針法
:param head:
:param n:
:return:
"""
pre_head = ListNode(0) # 定義一個臨時節(jié)點
pre_head.next = head # 將鏈表掛在臨時節(jié)點上话告，臨時節(jié)點成為頭節(jié)點
slw = fst = pre_head # 快慢指針開始位置都是臨時節(jié)點
i = 0
while i <= n and fst: # 快指針提前走n+1步兼搏，走到原鏈表第n個位置
fst = fst.next
i += 1
while fst: # 快慢指針同時走，直到快指針走到鏈表末尾
fst = fst.next
slw = slw.next
slw.next = slw.next.next # 把慢指針的下一個節(jié)點（倒數(shù)第n個節(jié)點）刪除
return pre_head.next
如有疑問或建議沙郭，歡迎評論區(qū)留言~
