[数据结构与算法]LeetCode19.删除链表的倒数第N个结点

LeetCode19.删除链表的倒数第N个结点

代码注释解析

/**
 * Definition for singly-linked list.
 * 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:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* newhead = new ListNode(0, head); //链表的初始化中节点的声明,新建一个头结点在head前
        int length = getLength(head);
        ListNode* cur = newhead;
        for (int i = 1; i < length - n + 1; ++i) {
            //找到被删除节点的前一个节点，前面已经声明了一个新的头结点，不会丢失头。
            cur = cur->next;
        }
        ListNode* del = cur->next;//断开删除节点
        cur->next = cur->next->next;
        ListNode* ans = newhead->next; //排除新节点。
        delete newhead;//清除内存
        delete del;
        return ans;
    }
};