C++进阶练习删除链表的倒数第N个结点详解

C++进阶练习删除链表的倒数第N个结点详解

问题描述

给定一个单向链表的头指针和一个整数 n，要求删除这个链表的倒数第 n 个节点。例如，链表为 1→2→3→4→5，n = 2 时，删除倒数第二个节点后的链表为 1→2→3→5。

解法思路

先让一个指针指向链表头节点，再让另一个指针从头节点开始向后移动 n-1 步，此时两个指针之间有 n-1 个节点。然后同时向后移动两个指针，直到第二个指针指向 NULL，此时第一个指针指向的节点就是倒数第 n 个节点。

我们可以设置一个哑节点 dummy，令其next指针指向head，然后设置两个指针p和q，一开始都指向哑节点。先将q指针向后移动n个节点，然后p和q同时后移，直到q指向最后一个节点时停止，那么此时p指向的节点就是要删除的节点的前一个节点。

代码实现

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

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* p = dummy;
    ListNode* q = dummy;

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

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

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

    return dummy->next;
}

示例说明

示例1

输入:

1->2->3->4->5, n = 2

输出:

1->2->3->5

解释:

删除链表的倒数第二个节点（结点值为4），输出链表为1->2->3->5。

示例2

输入:

1->2->3->4->5, n = 5

输出:

2->3->4->5

解释:

删除链表的倒数第五个节点（结点值为1），输出链表为2->3->4->5。