python怎么刪除鏈表的倒數(shù)第N個節(jié)點

【題目】

給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。

示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?nbsp;1->2->3->5.

說明：
給定的 n 保證是有效的。

進(jìn)階：
你能嘗試使用一趟掃描實現(xiàn)嗎？

【思路】

解法一：遍歷鏈表，得到鏈表長度N。那么刪除倒數(shù)第n個節(jié)點，即為刪除第N - n個節(jié)點。找到第N - n -1個節(jié)點，記為p，q = p.next, p.next=p.next.next, del p（記得清除內(nèi)存）。

唯一的問題是：如何刪除第1個元素，需要單獨判斷？可以不用這么麻煩：增加一個無意義的頭結(jié)點，所有的刪除邏輯都變成一致的了！

解法二：使用兩個指針first和second遍歷鏈表，首先，first指針前進(jìn)n步，second指針不變；緊接著，first指針和second指針同時前進(jìn)，直到first.next為None。此時，second指針指向的是倒數(shù)第n+1個節(jié)點，second.next = second.next.next同時刪除無用內(nèi)存即可。（刪除第1個元素的代碼邏輯與其它元素的不一樣，解決方法參考解法一的說明。）

【代碼】

python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 增加空的頭結(jié)點，使得邏輯一致
        node = ListNode(val=0, next=head)
        head = node
        
        # 找到第n-1個節(jié)點
        count = 0
        p = head
        while count < n:
            count += 1
            p = p.next
        
        # 找到倒數(shù)第n+1個節(jié)點
        q = head
        while p.next:
            p = p.next
            q = q.next
        
        # 刪除倒數(shù)第n個節(jié)點
        r = q.next
        q.next = q.next.next
        del r
        return head.next