19. 刪除鏈表的倒數(shù)第 N 個結(jié)點

已解答

中等

相關(guān)標(biāo)簽

相關(guān)企業(yè)

提示

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

# Definition for singly-linked list.

# class ListNode(object):

# ? ? def __init__(self, val=0, next=None):

# ? ? ? ? self.val = val

# ? ? ? ? self.next = next

class Solution(object):

? ? def removeNthFromEnd(self, head, n):

? ? ? ? """

? ? ? ? :type head: Optional[ListNode]

? ? ? ? :type n: int

? ? ? ? :rtype: Optional[ListNode]

? ? ? ? """

? ? ? ? # 用list很好實現(xiàn)

? ? ? ? # 可以雙指針，慢的慢n個，當(dāng)都到達的時候，就是對了

? ? ? ? low = head

? ? ? ? fast =head

? ? ? ? prev = None

? ? ? ? next_node = fast.next

? ? ? ? for i in range(n):

? ? ? ? ? ? fast = fast.next

? ? ? ? while fast!=None:

? ? ? ? ? ? prev = low

? ? ? ? ? ? low=low.next

? ? ? ? ? ? next_node = low.next

? ? ? ? ? ? fast = fast.next

? ? ? ?

? ? ? ? if prev!=None:

? ? ? ? ? ? prev.next=next_node

? ? ? ? ? ? return head

? ? ? ? else:

? ? ? ? ? ? return head.next

? ? ? ?

? ? ? ?

很簡單，可以用list直接做，高級做法是雙指針