算法: 移除单链表的倒数第N个节点 19. Remove Nth Node From End of List-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法: 移除单链表的倒数第N个节点 19. Remove Nth Node From End of List。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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.

Example 1:
算法: 移除单链表的倒数第N个节点 19. Remove Nth Node From End of List,算法,算法,list,数据结构

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

Follow up: Could you do this in one pass?

1. 计算总长度，减去N，即可得到顺序的需要跳过的节点

该方法采用了两次遍历链表的方法。首先，它计算链表的总长度，然后通过总长度减去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]:
        # 初始化一个哑节点，以便处理只有一个节点或需要删除头节点的情况
        dummy = ListNode(0)
        dummy.next = head
        first = dummy
        
        # 计算链表的长度
        l = 0
        while first:
            l += 1
            first = first.next
        
        # 计算需要删除的节点的正向位置
        l -= n
        first = dummy
        
        # 移动first指针到要删除的节点的前一个节点
        while l > 1:
            l -= 1
            first = first.next
        
        # 删除节点
        first.next = first.next.next

        # 返回哑节点的下一个节点，即为新的头节点
        return dummy.next

复杂度分析:

时间复杂度:
O(n)：我们遍历了链表两次，其中n是链表的长度。所以总体时间复杂度是2n，但常数因子被忽略了，所以时间复杂度仍然是O(n)。

空间复杂度:
O(1)：我们只使用了常数个额外的空间。
这种方法虽然需要遍历两次链表，但它在逻辑上更直接，有时可能更容易理解。

2. 双指针解法，保持N的距离

方法是使用两个指针，并使第一个指针比第二个指针提前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]:
        # 初始化一个哑节点，以便处理只有一个节点或需要删除头节点的情况
        dummy = ListNode(0)
        dummy.next = head
        first, second = dummy, dummy

        # 移动first指针，使其与second指针之间的距离为n
        for i in range(n+1):
            first = first.next
        
        # 同时移动first和second指针，直到first指针到达链表的末尾
        while first:
            first = first.next
            second = second.next
        
        # second指针现在指向倒数第n+1个节点，删除其后面的节点即可
        second.next = second.next.next

        # 返回哑节点的下一个节点，即为新的头节点
        return dummy.next