删除链表的倒数第n个节点

标签：head ListNode next 链表 节点 倒数第 first

• 描述

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如， 给出的链表为: 1→2→3→4→5,n=2.
删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5.   数据范围： 链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100 要求：空间复杂度 O(1)，时间复杂度 O(n)
备注： 题目保证n 一定是有效的  

• 示例

输入：{1,2},2 输出：{2}   

• 算法思想

先将链表逆置，采用头插法的思想逆置链表，然后删除正数第n个节点，最后再将链表逆置并返回   代码 

 1 #include <cstdlib>
 2 class Solution {
 3 public:
 4     /**
 5      * 
 6      * @param head ListNode类 
 7      * @param n int整型 
 8      * @return ListNode类
 9      */
10      //逆置链表(头插法)
11      ListNode* reverse(ListNode *head){
12         ListNode *first=(ListNode*) malloc(sizeof(ListNode));
13         first->val=0;
14         first->next=nullptr;
15         while(head){
16             ListNode *temp=head->next;
17             head->next=first->next;
18             first->next=head;
19             head=temp;
20         }
21         return first;
22      }
23      //删除倒数第n个节点
24     ListNode* removeNthFromEnd(ListNode* head, int n) {
25         ListNode *L1=reverse(head);
26         ListNode *p=L1;
27         for(int i=1;i<n;i++){
28             p=p->next;
29         }
30         ListNode *q=p->next;
31         p->next=q->next;
32         free(q);
33         ListNode *L2=reverse(L1->next);
34         return L2->next;
35     }
36 };

 

      

标签：head,ListNode,next,链表,节点,倒数第,first
From： https://www.cnblogs.com/yueshengd/p/17487743.html