题目
给你一个链表,删除链表的倒数第 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]
分析
可以先求链表长度length,然后向后走length - n步找到待删元素的前一位,但是至少要两次遍历链表;
使用快慢指针法可以一次遍历找到待删元素
图解
上述思路有一个问题,当n = k, 即待删除元素时第一个结点时,需要另外讨论,为了对所有节点统一处理,简化操作,使用一个伪结点技巧,即插入一个伪结点dummy,它的next指向head.,其他过程完全不变,如下:
图解
代码
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummpy = new ListNode(0); dummpy->next = head; ListNode* fast = dummpy; ListNode* slow = dummpy; while (n--) { fast = fast->next; } fast = fast->next; //fast先走n+1步 while (fast != NULL) { fast = fast->next; slow = slow->next; } //此时slow指向待删除的前一个结点 slow->next = slow->next->next; return dummpy->next; } };