[数据结构与算法]Leetcode第十九题(删除链表的倒数第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]

?暴力求解:

? ? ? ? 先找到链表的长度L,?那么应该删除的节点就是第L -?n + 1,?但是我们需要找的是删除节点的前一个节点.因此循环次数为L -?n 次

?

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* retNode = new ListNode;
        retNode->next = head;
        ListNode* dummp = retNode,*curNode = retNode;
        //遍历一次链表,得到链表的长度
        int L = 0;
        while(curNode->next){
            L++;
            curNode = curNode->next;
        }
        //寻找删除节点的前一个节点
        L = L - n;
        while(L--){
           dummp = dummp->next;
        }
        //删除节点
        dummp->next = dummp->next->next;

        return retNode->next;
    }
};

?快慢指针:

????????利用快慢指针的方式,?先同时让快指针(fast)与慢指针(slow)指向一个创建的虚拟节点(retNode),?retNode的next域指向头节点(head),?使用虚拟节点的好处是减少对头节点(head)的边界判断以及处理,?然后快指针向后移动n个节点,?随后快慢指针一起向后移动直到快指针(fast)的next域为NULL,?说明此时快指针已经移动到了最后一个节点,?此时慢指针(slow)即为要删除节点的前一个节点,?直接删除掉慢指针(slow)节点的下一个节点,?最后返回虚拟节点(retNode)的next即可.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* retNode = new ListNode;
        retNode->next = head;
        ListNode* slow = retNode,*fast = retNode;
        while(n--)
            fast = fast->next;
        while(fast->next){
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;

        return retNode->next;
    }
};