题目
给你一个链表，删除链表的倒数第 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]
解题:
方法一：计算链表长度
# 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: ListNode, n: int) -> ListNode: #l为链表长度 current = head l = 0 while current: current = current.next l+=1 dummy = ListNode(0,head) current = dummy for _ in range(0,l-n): current = current.next current.next = current.next.next return dummy.next
方法二：堆栈
我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 nn 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。
python解法
class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: dummy = ListNode(0, head) stack = list() cur = dummy while cur: stack.append(cur) cur = cur.next for i in range(n): stack.pop() prev = stack[-1] prev.next = prev.next.next return dummy.next
c++解法
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { stack<ListNode*> stack; ListNode* dummy=new ListNode(0,head); ListNode* cur=dummy; while(cur){ stack.push(cur); cur=cur->next; } while(n--){ stack.pop(); } ListNode* tmp=stack.top(); tmp->next=tmp->next->next; return dummy->next; } };
方法三：双指针一次遍历
python解法
class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: dummy = ListNode(0,head) first = head second = dummy for _ in range(n): first = first.next while first: second = second.next first = first.next second.next = second.next.next return dummy.next
c++解法
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy=new ListNode(0,head); ListNode* slow=dummy; ListNode* fast=head; while(n--){ fast=fast->next; } while(fast){ slow=slow->next; fast=fast->next; } slow->next=slow->next->next; return dummy->next; } };
java解法
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy=new ListNode(0); dummy.next=head; ListNode slow=dummy; ListNode fast=head; for(int i=0;i<n;i++){ fast=fast.next; } while(fast!=null){ slow=slow.next; fast=fast.next; } slow.next=slow.next.next; return dummy.next; } }
因为要删除的节点，只有知道前一个节点才能把它删除，因此first和second之间要有n个节点
