PhyCmdBlock的做题笔记

外观

19. 删除链表的倒数第 N 个结点 ​

力扣题目链接

我的初版代码 ​

cpp
class Solution {
  public:
	ListNode *removeNthFromEnd(ListNode *head, int n)
	{
		ListNode *p = head;
		for (int i = 0; i < n;
			 i++) { // p先走n步，然后q在起步，这样q就是要删的结点前面
			p = p->next;
		}

		if (p == nullptr) {
			return head->next;
		}

		ListNode *q = head;
		while (p->next != nullptr) {
			q = q->next;
			p = p->next;
		}
		q->next = q->next->next;
		return head;
	}
};

我一开始就想到了，快慢指针，让一个指针先走n步，在前面探路，然后一个慢的指针和它同步往后走，快指针探到末尾了，慢指针就可以删结点了。

具体解释数量关系：p和q初值都是在第1个结点上面。p最终会在最后1个结点上停下（p不会等到自己是null再停）。p会提前走n步，这样最终状态下，p在倒数第1个结点上，q在倒数第n+1个结点上，是n前面那个，这样才能删了n。

但是我在过程中发现了明显的问题，就是题目用的是没有头结点的，这个就需要修改头指针，然后我就找ai求助了，ai就只给我加了一句

cpp
if (p == nullptr) {
	return head->next;
}

这个给人的感觉就很不好，好像走n步让p走出去了就意味着是删第一个结点一样。在这个题里确实是这样，但不符合逻辑。这样写确实能过。

加个虚拟头结点 ​

实际上，题目没有头结点的话，你可以自己加一个头结点，加了头结点以后逻辑就会很顺。

这样快慢指针都从头结点出发。这个人的写法跟我上面那种不一样，快指针会在自己为null的时候才停下来。这样快指针就得走n+1步（快指针在倒数第1个结点的后面，可以理解为倒数第0个，然后慢指针在倒数第n+1个，殊途同归，和上面我的一样了）。然后依旧是快慢指针同时出发，快指针指null停，然后慢指针改next。这个就不需要去考虑头指针，因为有头结点，慢指针指在头结点就可以改。最后你return就只用return头结点的next。

代码来源

cpp
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next; 
        
        // ListNode *tmp = slow->next;  C++释放内存的逻辑
        // slow->next = tmp->next;
        // delete tmp;
        
        return dummyHead->next;
    }
};

提醒 ​

这里是因为交LeetCode代码，没把删掉的元素内存释放掉，真实情况要去释放一下。