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.
For example, Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
• Given n will always be valid.
• Try to do this in one pass.

二. 題目分析

給出一個鏈表， n是指刪除倒數第n個節點。這裡的提示n的值默認是合法的。不過其實對輸入的n進行異常判斷也只需要幾句語句。

使用兩個指針，即快/慢指針的概念，其中一個指針先走n步，然後慢指針走，等到快指針走到結尾時，那麼慢指針走到了需要刪除的節點的前一個位置。

這道題主要難點是考慮邊界問題，以及特殊情況（要刪除的是頭節點），如輸入1->2->3->4， n=4，那麼需要刪除1，此時只需將頭指針head = head->next就可以了。

三. 示例代碼

#include 

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

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        if (head == NULL)
            return NULL;
        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *temp = head;
        for (int i = 0; i < n ; i++)
        {
            fast = fast->next;
            if (fast)
                continue;
            else break;
        }
        while (fast)
        {
            fast = fast->next;
            temp = slow;
            slow = slow->next;
        }
        if (slow == head)
        {
            head = head->next;
            return head;
        }
        temp->next = slow->next;
        delete slow;
        return head;
    }
};

結果：

編程中經常會遇到邊界問題，不小心的錯誤很容易造成程序奔潰，關於指針和鏈表的使用技巧還需要進一步的學習。