巧删链表倒数第N节点（一种语言三种解法）

题目给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。示例1输入head [1,2,3,4,5], n 2输出[1,2,3,5]Python解法解法一两次遍历class Solution: def removeNthFromEnd(self, head: ListNode, n: int) - ListNode: # 1. 求链表长度 def get_len(head): length 0 while head: length 1 head head.next return length # 哑节点处理删除头节点的情况 dummy ListNode(0, head) length get_len(head) cur dummy # 走到【倒数第n个节点】的前一个 for _ in range(length - n): cur cur.next # 删除节点 cur.next cur.next.next return dummy.next1get_len函数从头走到尾数链表节点的个数返回长度。2dummy ListNode0head造一个虚拟的头节点next指向真实的头节点。如果删除第一个也能统一处理不用单独写代码。3创建cur用cur来进行删除链表dummy来进行返回链表。解法二栈方法class Solution: def removeNthFromEnd(self, head: ListNode, n: int) - ListNode: dummy ListNode(0, head) stack [] cur dummy # 把所有节点压入栈 while cur: stack.append(cur) cur cur.next # 弹出 n 个节点就是倒数 n 个 for _ in range(n): stack.pop() # 栈顶就是要删除节点的**前一个节点** prev stack[-1] prev.next prev.next.next return dummy.next把链表全部压入栈栈顶就是最后一个节点弹出 n 个剩下的栈顶就是倒数第 n1 个节点直接删除它后面那个节点就行注意stack.pop这一步弹出的只是 “栈里的引用记录”原链表的 5、4 节点依然存在没有被删除 / 丢失。解法三快慢指针class Solution: def removeNthFromEnd(self, head: ListNode, n: int) - ListNode: dummy ListNode(0, head) fast head slow dummy # 快指针先走 n 步 for _ in range(n): fast fast.next # 快慢一起走直到 fast 为空 while fast: fast fast.next slow slow.next # 删除节点 slow.next slow.next.next return dummy.next让快指针先走 n 步然后快慢一起走等快指针走到头慢指针正好停在要删除节点的前一个。要让slow停在「倒数第 n 个节点的前驱」必须满足fast 走过的总步数 slow 走过的总步数 nJava解法这里只展示快慢指针class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode slow dummy; ListNode fast dummy; for (int i 0;i n ; i){ fast fast.next; } while(fast.next!null){ fast fast.next; slow slow.next; } slow.next slow.next.next; return dummy.next; } }C语言解法同Java解法struct ListNode* createNode(int val) { struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next NULL; return node; } // 快慢指针删除倒数第n个节点 struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { // 1. 创建虚拟头节点解决删除头节点的边界问题 struct ListNode* dummy (struct ListNode*)malloc(sizeof(struct ListNode)); dummy-val 0; dummy-next head; // 2. 初始化快慢指针都指向虚拟头节点 struct ListNode* fast dummy; struct ListNode* slow dummy; // 3. 快指针先走n步 for (int i 0; i n; i) { fast fast-next; // 题目保证n有效此处省略n越界判断 } // 4. 快慢指针同步移动直到快指针到链表末尾 while (fast-next ! NULL) { fast fast-next; slow slow-next; } // 5. 定位到待删节点释放内存并删除 struct ListNode* toDelete slow-next; // 保存待删节点地址用于释放 slow-next slow-next-next; // 跳过待删节点 free(toDelete); // C语言需手动释放内存避免内存泄漏 // 6. 保存新的头节点释放虚拟头节点避免内存泄漏 struct ListNode* newHead dummy-next; free(dummy); return newHead; } // 打印链表辅助函数方便测试 void printList(struct ListNode* head) { struct ListNode* cur head; while (cur ! NULL) { printf(%d , cur-val); cur cur-next; } printf(\n); }总结此题方法多样其中快慢指针方法最为好用快指针先向前移动n步随后快慢指针同步向后遍历当快指针到达链表末尾时慢指针恰好指向「倒数第 N 个节点的前驱节点」直接跳过目标节点即可完成删除。