leetcode刷题：删除链表的倒数第 N 个结点

leetcode刷题：删除链表的倒数第 N 个结点

题目：

采取双重遍历肯定是可以解决问题的，但题目要求我们一次遍历解决问题，那我们的思路得发散一下。

我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。

设置虚拟节点 dummyHead 指向 head
设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
移动 q，直到 p 与 q 之间相隔的元素个数为 n
同时移动 p 与 q，直到 q 指向的为 NULL
将 p 的下一个节点指向下下个节点

代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
     ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* p = dummyHead;
        ListNode* q = dummyHead;
        for( int i = 0 ; i < n + 1 ; i ++ ){
            q = q->next;
        }

        while(q){
            p = p->next;
            q = q->next;
        }

        ListNode* delNode = p->next;
        p->next = delNode->next;
        delete delNode;

        ListNode* retNode = dummyHead->next;
        delete dummyHead;

        return retNode;
        
    }
};

整体项目测试代码：

#include 
using namespace std;


struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
};


class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
     ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* p = dummyHead;
        ListNode* q = dummyHead;
        for( int i = 0 ; i < n + 1 ; i ++ ){
            q = q->next;
        }

        while(q){
            p = p->next;
            q = q->next;
        }

        ListNode* delNode = p->next;
        p->next = delNode->next;
        delete delNode;

        ListNode* retNode = dummyHead->next;
        delete dummyHead;

        return retNode;

    }
    ListNode *createNode()
    {
	    ListNode *head = new ListNode();
	    ListNode *temp = head;
	    for(int i = 1; i<5; i++)
	    {
		ListNode *a = new ListNode();
		a->val = i;
		a->next = NULL;
		temp->next = a;
		temp = temp->next;
	    }
	    return head;
    }

    void display(ListNode *p)
    {
	    ListNode *temp = p;
	    while(temp->next)
	    {
		    temp = temp->next;
		    cout <<"value:"<val;
	    }
	    cout << endl;
    }
};



int main()
{
	Solution way;
	ListNode *head = way.createNode();
	way.display(head);
	ListNode *modifyhead = way.removeNthFromEnd(head,2);
	way.display(modifyhead);

}