[数据结构与算法]数据结构与算法15（删除链表的倒数第 n 个结点）

1 问题

?????? 给定一个链表，删除链表的倒数第?n?个结点，并且返回链表的头结点。

1.1 示例

????????输入：head = [1,2,3,4,5], n = 2

????????输出：[1,2,3,5]

2 思路

2.1 遍历

??????? 由于头结点可能被删除，所以我们增加一个dummy结点；首先确定整个链表的长度len，最后找到倒数第n个结点的前一个结点（len-n-1），删除就行了。

2.2 快慢双指针

??????? 令快慢双指针之间间隔n-1个结点，这样当快结点到达链表尾部的时候，慢结点既是倒数第n个结点的前一个结点，删除就行了。

3 编程

3.1 遍历

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* dummy = new ListNode(0, head);
        ListNode* prev = dummy;
        ListNode* temp1 = prev;
        ListNode* temp2 = prev;
        int len = 0;
        while(temp1)
        {
            temp1 = temp1->next;
            len++;
        }

        for (int i=0; i<(len-n-1); i++)
        {
            temp2 = temp2->next;
        }
        
        temp2->next = temp2->next->next;

        return dummy->next;
 
    }
};

3.2 快慢双指针

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* dummy = new ListNode(0, head);
        ListNode* slow = dummy;
        ListNode* fast = head;

        for (int i=0; i<n; i++)
        {
            fast = fast->next;
        }

        while (fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        slow->next = slow->next->next;
        return dummy->next;
    }
};