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

1. 题目给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。示例 1输入head [1,2,3,4,5], n 2输出[1,2,3,5]示例 2输入head [1], n 1输出[]示例 3输入head [1,2], n 1输出[1]2. 题解2.1. 计算2.1.1. 核心思想链表只能向后遍历不能直接访问倒数位置没有下标。 倒数第n个结点 ⇔正数第总长度 − n 1 个结点。例链表[1,2,3,4,5]长度count5删除倒数第 2 个 (4)count‑n 5‑2 3→ 正数第 3 个结点 (3)是待删节点的前驱。 让前驱结点的 next跳过待删结点cur-next cur-next-next。2.1.2. 代码/** * 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) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);ListNode*curhead;intlen0;while(cur){len;curcur-next;}curdummy;// 走到待删节点的前驱len-n步for(inti0;ilen-n;i){curcur-next;}ListNode*delcur-next;cur-nextcur-next-next;deletedel;ListNode*ansdummy-next;deletedummy;returnans;}};2.1.3. 复杂度时间复杂度O ( L ) O(L)O(L)L 是链表长度完整遍历 2 次链表空间复杂度O ( 1 ) O(1)O(1)只用几个指针、计数器变量2.2. 栈2.2.1. 核心思想栈后进先出。 把链表所有节点依次压入栈中栈底是头结点栈顶是尾结点。 弹出 n 个节点弹出的第 1 个就是要删除的倒数第 n 个结点。 此时栈顶剩下的元素就是待删节点的前驱结点。 然后修改前驱的 next跳过被删除节点。边界如果弹完 n 个之后栈为空说明要删的是头结点。2.2.2. 代码/** * 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) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){stackListNode*st;ListNode*curhead;while(cur!nullptr){st.push(cur);curcur-next;}ListNode*delnullptr;for(inti0;in;i){delst.top();st.pop();}if(st.empty()){headhead-next;}else{ListNode*prest.top();pre-nextpre-next-next;}deletedel;returnhead;}};2.2.3. 复杂度时间复杂度O ( L ) O(L)O(L)L 链表长度。遍历一次链表入栈再弹出 n 次。空间复杂度O ( L ) O(L)O(L)需要栈存储全部链表节点。2.3. 双指针2.3.1. 核心思想利用两个指针保持固定间隔 n。 快指针先往前走n 步之后快慢指针同步一起往后走。 当快指针走到链表末尾 (nullptr) 时慢指针恰好落在待删除节点的前驱结点。为什么可以这样 倒数第 n 个节点距离链表末尾空指针的距离正好是 n。 让快指针先拉开 n 的距离再同速前进快指针碰到底慢指针就定位到目标前驱。必须搭配dummy 虚拟头结点规避删除头结点的特殊边界。 如果不用 dummy删除头节点的情况要额外 if 判断。2.3.2. 代码/** * 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) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);ListNode*fastdummy;ListNode*slowdummy;for(inti0;in;i){fastfast-next;}while(fast-next!nullptr){fastfast-next;slowslow-next;}ListNode*delslow-next;slow-nextslow-next-next;deletedel;ListNode*resdummy-next;deletedummy;returnres;}};2.3.3. 复杂度时间复杂度O ( L ) O(L)O(L)只遍历链表一遍。总共移动指针 L 次空间复杂度O ( 1 ) O(1)O(1)仅几个指针变量常数空间。2.4. 三种算法对比方法时间空间特点计数两次遍历O(L)O(1)直观遍历两遍要处理头结点边界栈O(L)O(L)利用后进先出逻辑简单额外占用内存快慢指针O(L)O(1)一次遍历双指针距离差最优3.19. 删除链表的倒数第 N 个结点 - 力扣LeetCode