Leetcode-每日一题【19.删除链表的倒数第N个结点】

**LeetCode 每日一题: 删除链表的倒数第 N 个结点**

### 题目描述给定一个单链表的头指针 `head` 和一个整数 `n`,请将列表中从头部到倒数第 `n` 个结点的所有结点删除。

示例1:

输入: head = [1,2,3,4,5], n =2输出: [1,2,3,5]

示例2:

输入: head = [1], n =1输出: []

### 解决方案#### 方法一: 双指针法我们可以使用双指针法来解决这个问题。首先，我们需要找到链表的长度 `length`。然后，我们可以将两个指针 `p1` 和 `p2` 都设置为链表的头结点 `head`。

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef removeNthFromEnd(head: ListNode, n: int) -> ListNode:
 # 找到链表的长度 length =0 temp = head while temp:
 length +=1 temp = temp.next # 如果删除的是头结点 if length == n:
 return head.next # 初始化两个指针 p1 = head for _ in range(length - n -1):
 p1 = p1.next # 删除倒数第 N 个结点 p1.next = p1.next.next return head

#### 方法二: 迭代法我们可以使用迭代法来解决这个问题。首先，我们需要找到链表的长度 `length`。然后，我们可以将一个指针 `p` 设置为链表的头结点 `head`,并且将另一个指针 `q` 也设置为链表的头结点 `head`。

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
 # 找到链表的长度 length =0 temp = head while temp:
 length +=1 temp = temp.next # 如果删除的是头结点 if length == n:
 return head.next # 初始化两个指针 p = head for _ in range(length - n):
 p = p.next # 删除倒数第 N 个结点 p.next = p.next.next return head

#### 方法三: 递归法我们可以使用递归法来解决这个问题。首先，我们需要找到链表的长度 `length`。然后，我们可以将一个指针 `p` 设置为链表的头结点 `head`,并且将另一个指针 `q` 也设置为链表的头结点 `head`。

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
 # 找到链表的长度 length =0 temp = head while temp:
 length +=1 temp = temp.next # 如果删除的是头结点 if length == n:
 return head.next # 初始化两个指针 p = head for _ in range(length - n):
 p = p.next # 删除倒数第 N 个结点 p.next = p.next.next return head

### 总结删除链表的倒数第 N 个结点是一个经典的问题，涉及到链表的遍历和修改。我们可以使用双指针法、迭代法或递归法来解决这个问题。每种方法都有其优缺点，我们需要根据具体情况选择合适的方法。

###代码注释* `removeNthFromEnd` 是一个函数，用于删除链表的倒数第 N 个结点。
* `head` 是一个 ListNode 对象，表示链表的头结点。
* `n` 是一个整数，表示要删除的结点的位置。
* `length` 是一个变量，表示链表的长度。
* `p1` 和 `p2` 是两个指针，用于遍历链表。
* `temp` 是一个临时变量，用于存储当前结点。

### 示例代码

# 创建一个链表：[1,2,3,4,5]
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# 删除倒数第2 个结点n =2# 调用函数删除链表的倒数第 N 个结点new_head = removeNthFromEnd(head, n)

# 打印新链表while new_head:
 print(new_head.val)
 new_head = new_head.next

### 最终结果最终结果是：[1,2,3,5]