19.Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.
给定一个链表，从后往前数，删除第n个元素

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

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

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

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

思考

这边已经给定了链表的结构

# Definition for singly-linked list.
 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next

并没有个数，只有下一个，和当前值。
按理说这样的链表想要找到最后只能够挨个遍历下去，但是又不想来回遍历第二遍去删除倒数第N个数据。那只能用到递归的做法。

# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
        one =  bool(head.next)
            
        def findNth(head: Optional[ListNode], n: int, i: int):
            if bool(head.next):
                
                i = findNth(head.next, n, i)
                
                if n == i:
                    head.next = head.next.next
                    
                return i+1
            else:
                return 1

                
        i = findNth(head,n, 0)
        
        if n==1 and not one:
            head = None
        elif n == i:
            head.val =head.next.val
            head.next = head.next.next
            
        return head
        

磕磕碰碰的做完了，但是并没有用到很好的算法。主要难点在一对前后端点的删除。

答案解析

答案是从力扣中国里面查看的，美国站不充会员还不能看。。
这边给了三种解决方案

计算链表长度（暴力法）

直接从头到尾先计算总长度，再遍历第二次删除需要删除的那一节。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def getLength(head: ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        
        dummy = ListNode(0, head)
        length = getLength(head)
        cur = dummy
        for i in range(1, length - n + 1):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next

时间复杂度L+n

栈

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        stack = list()
        cur = dummy
        while cur:
            stack.append(cur)
            cur = cur.next
        
        for i in range(n):
            stack.pop()

        prev = stack[-1]
        prev.next = prev.next.next
        return dummy.next

将链表依次放入栈中，根据先入后出的原则，现将所有的链表全部放入list中，再删除第n个出的节点。
栈的方法和我有点像。虽然我的也能完成，但是就没有用栈这么漂亮。

双指针

这题我还专门想了一下能不能用双指针，最后没用上。看来还是自己没学到家。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next

        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        return dummy.next

定义两个指针，第一个指针指向头节点，第二个指针指向头节点前一个节点。第一遍，现将first节点走n编。第二遍将first和second节点一起走，走完之后的second节点就相当于找到了倒数第N+1个节点。
时间复杂度L

总结

不得不说最后的双指针算法是真的漂亮。得学习才行