原题链接

题目描述

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

示例

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

note

给定的 n 保证是有效的。

思路

遍历两次列表。第一遍历用于求出链表的长度，然后第二次遍历节点指针到处，把第的节点的next连接到第节点。复杂度 **** 。
注意编写接口时的边界处理，一开始在NULL处疯狂WA。

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
        ListNode *cntnode = head, *prenode = head;
        int length = 0, cnt = 0;
        while (cntnode) {
            ++length;
            cntnode = cntnode->next;
        }
        length -= n;
        if (!length){
            head = head->next;
            return head;
        }
        while (--length) {
            prenode = prenode->next;
        }
        auto x = prenode->next;
        prenode->next = x->next;
        delete x;
        return head;
    }
};