動機

對ㄟ，可以先拉一個範圍去走，有點像求中點

Problem

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Example 1:

Input: head = [1,2,3,4,5], n = 2Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1Output: []

Example 3:

Input: head = [1,2], n = 1Output: [1]

 

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

 

Follow up: Could you do this in one pass?

Sol

可以用遞迴的後半段來刪node

def main(prev,head,n):
    if not head:
        return [head,n-1]
    else:
        prev_head, n = main(head, head.next, n)
        if n == 0:
            if prev:
                prev.next = head.next
                return [prev, -1]
            else:
                return [head.next, -1]
        else:
            return [head, n-1]
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        head, n = main(None, head, n)
        return head

或者，先把距離拉出來 讓終點ptr與要刪的點先保持需要的距離

之後讓終點ptr走到底，再刪

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        prev, now, end = None, head, head
        for _ in range(n):
            end = end.next
        
        while end:
            prev, now, end = now, now.next, end.next
        
        if prev:
            prev.next, ret = now.next, head
        else:
            ret = now.next
        return ret