删除链表倒数第N个结点

删除链表的倒数第N个结点

1、题目

图1

2、题解

辅助空间法

将链表的值存入数组中，跳过对应节点的值，将剩余值存入新的链表，最终返回新链表

# 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]:
        res = ListNode(-1)
        dummy = res
        h_val = []
        while head:
            h_val.append(head.val)
            head = head.next
        for i in range(len(h_val)):
        
            if i == len(h_val) - n:
                continue
            res.next = ListNode(h_val[i])
            res = res.next
            
        return dummy.next

双指针

设置双指针a、b，当b指向末尾None，两个指针间隔元素为n时，删除a的下一个指针即可

# 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]:
        res = ListNode(-1)
        res.next = head
        a,b = res,res

        for _ in range(n):
            b= b.next
        while b and b.next:
            a = a.next
            b = b.next
        a.next = a.next.next

        return res.next