19. 刪除鏈表的倒數第 N 個結點 - 力扣（LeetCode）https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-100-liked

計算鏈表長度

對于鏈表，難的就是不知道有多少元素，所以先遍歷一次鏈表得到元素個數，然后根據要刪除的位置可以在再一次遍歷時找到刪除的元素的前一個元素位置。需要注意的是若要求刪除的是第一個元素，因為第一個元素前沒有 元素，所以不好操作，因此我們手動設置一個頭指針指向第一個元素。

//c++
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* h=new ListNode(0,head);ListNode* a=h;int m=0;while(head){m=m+1;head=head->next;}for(int i=0;i<m-n;i++)  a=a->next;a->next=a->next->next;return h->next;}
};#python
# 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]:m=0h=headwhile h:m=m+1h=h.nexth=ListNode(0,head)a=hfor i in range(m-n):a=a.nexta.next=a.next.nextreturn h.next

棧

有一種數據結構是后進先出，代入這道題完美適應，所以遍歷鏈表，使元素入棧，注意這里也要加入頭指針指向第一個元素，然后根據倒數第幾個元素要刪除的去出棧，最后選取棧頂元素也就是要刪除元素的前一個元素進行 操作。

//c++
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* h=new ListNode(0,head);ListNode* a=h;stack<ListNode*> m;while(a){m.push(a);a=a->next;}for(int i=0;i<n;i++)  m.pop();ListNode* b=m.top();b->next=b->next->next;return h->next;}
};#python
# 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]:h=ListNode(0,head)a=hm=list()while a:m.append(a)a=a.nextfor i in range(n):m.pop()b=m[-1]b.next=b.next.nextreturn h.next

雙指針

?最喜歡這個解法，巧妙，且只需遍歷一次鏈表，雖然兩次和一次也沒差。。

要加頭指針！

就是兩個指針，并保證這兩個指針中間間隔要求的倒數n個元素，然后在快的指針到達鏈表尾部時，慢的指針自然而然就在要刪除元素的前一個元素的位置了。

//c++
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* h=new ListNode(0,head);ListNode* a=h;ListNode* b=head;for(int i=0;i<n;i++)  b=b->next;while(b){a=a->next;b=b->next;}a->next=a->next->next;return h->next;}
};#python
# 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]:h=ListNode(0,head)a=hb=headfor i in range(n):b=b.nextwhile b:a=a.nextb=b.nexta.next=a.next.nextreturn h.next