[LeetCode]Remove Nth Node From End of List

原题

Given a linked list, remove the n -th node from the end of list and return its head.

Example:

Given linked list: <strong>1->2->3->4->5</strong>, and <strong><em>n</em> = 2</strong>.

After removing the second node from the end, the linked list becomes <strong>1->2->3->5</strong>.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

思路

首先，明确题意。题目给出了一个只有后继（successor），没有前驱（predecessor）的一个单向链表。要求删除倒数第n个节点。

那么，思路自然会想到的就是在一次遍历就搞定题目要求。所以，我们自然要在遍历的过程中保存一些状态值。那么，这个状态值无非就是目标节点（要删除节点，即第n个节点）的 前驱 。这样，才能将目标节点干掉。

那么，在遍历时，达到目标节点前驱的条件（时刻）是什么？即

cur_l - n > 0

`cur_l`指的是当前遍历的节点个数（即长度），n即题目指定的入参。细细品味，即可明白。

代码

/**
 * 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) {
        auto cur_node = head, search_node = head;
        int cur_l = 1;
        while (cur_node->next != NULL) {
            cur_node = cur_node->next;
            if (++cur_l - n > 1) search_node = search_node->next;
        }
        if (cur_l - n > 0) {
            search_node->next = (search_node->next == NULL) ? NULL : search_node->next->next;
        } else {
            head = head->next;
        }
        return head;
    }
};

原题： https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

文章来源： 胡小旭 => [LeetCode]Remove Nth Node From End of List