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

题目
给你一个链表,删除链表的倒数第 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步找到待删元素的前一位,但是至少要两次遍历链表;
使用快慢指针法可以一次遍历找到待删元素

图解
LeetCode 19.删除链表的倒数第N个结点

 上述思路有一个问题,当n = k, 即待删除元素时第一个结点时,需要另外讨论,为了对所有节点统一处理,简化操作,使用一个伪结点技巧,即插入一个伪结点dummy,它的next指向head.,其他过程完全不变,如下:

图解

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

代码

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;
    }
};

 

上一篇:第四届 美团MTCTF Write-up(Crypto) by Schen


下一篇:【ISO14229_UDS诊断】-11.18-$19服务sub-function = 0x13 reportEmissionsOBDDTCByStatusMask