删除单链表的倒数第n个节点

• 题目
• 解决思路
• 代码
• 说明

题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。示例如下：

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

解决思路

• 思路： 先定位到要删除的节点的上一个节点，然后删除需要删除的节点。
• 步骤：
  • 定义两个指针p和q，p指向虚拟头节点，q指向p的下一个节点。
  • 先让指针q向前走n步，然后p和q同时向前移动。
  • 当q指向null时，p指向的节点为要删除的节点的上一个节点。
  • 删除p的下一个节点。

代码

• C++代码

// 删除链表的倒数第 n 个结点，并且返回链表的头结点。
// 对应LeetCode第19题
// 网址：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

# include <stdio.h>

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


class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    	if (nullptr == head) {
            return head;
        }
        // 先判断链表的长度和n的大小，如果n大于链表的长度，则返回null
        int num = 0;    // 记录链表的长度
        ListNode *h = head;
        while (h) {
            h = h->next;
            num++;
        }
        if (n > num) {  // 如果n大于链表的长度，则返回null
            return nullptr;
        }

        ListNode ret(0, head);  // 虚拟头结点
        ListNode *p = &ret;
        ListNode *q = p->next;

        // 先让q向前走n步
        while (n--) {
            q = q->next;
        }
        // p和q一起移动，直到q指向null
        while (q) {
            p = p->next;
            q = q->next;
        }
        p->next = p->next->next;
        return ret.next;
    }

};


int main() {
    ListNode *a = new ListNode(1);
    ListNode *b = new ListNode(2);
    ListNode *c = new ListNode(3);
    ListNode *d = new ListNode(4);
    ListNode *e = new ListNode(5);
    ListNode *head = a;

    a->next = b;
    b->next = c;
    c->next = d;
    d->next = e;

    printf("before delete: ");
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");

    head = a;

    int n = 2;
    Solution *solutioin = new Solution();
    ListNode *ret = solutioin->removeNthFromEnd(head, n);
    printf("after delete: ");
    while (ret) {
        printf("%d ", ret->val);
        ret = ret->next;
    }

    return 0;
}

说明

• 对应LeetCode第19题。
• 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/