筆試題32. LeetCode OJ (19)

終於碰見了和數據結構相關的題目了，這也意味著復雜度在增加。來看看這道題吧，刪除鏈表的倒數第k個節點，我們有必要先找出鏈表的長度然後再確定倒數第k個節點嗎？我覺得這是沒必要的。因為我們的方法比這樣更巧，聽起來高大尚一些。解題思路以及注意事項如下：

1.我采用的是兩個指針，一快一慢，快的先走k+1步，然後快指針和慢指針一起走，直到快指針走到尾

2.為什麼要快指針要走k+1步呢？我們仔細想想一下，我們是通過慢指針來決定要刪除的節點的，如果慢指針剛剛好指在要刪除的節點上，那麼恭喜你，你需要再遍歷一遍鏈表，找到慢指針的前一個節點，然後刪掉慢指針，最後鏈接鏈表。

3.所以快指針 fast 走k+1步是有道理的，這種情做法需要考慮一種特殊情況，那就是要刪除的是頭結點的情況，我解決的辦法是利用fast指針終止的位置來判斷的，即：

int m=K+1;
while(m && fast)
{
	fast = fast->next;
	--m;
}

(1).若m>1,那麼說明鏈表長度不夠，直接退出

(2).若m==1，這就說明要刪除的節點是頭結點，這時候把頭節點指向下一個節點然後返回

(3).其他情況則很簡單，慢指針指向要刪除的節點的前一個節點，我們正常處理就行了

所以整個代碼如下：

/**
 * 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) {
        //刪除鏈表的倒數第n個節點，這個題的思路是快慢指針，快指針先走n步，然後快慢一起走
        if(head == NULL || n < 0)
        {
            return NULL;
        }
        ListNode *fast=head;
        ListNode *slow=head;
        int m=n+1; //返回被刪除位置的前一個位置
        while(fast && m)
        {
            fast=fast->next;
            --m;
        }
        if(m >1)
        {//鏈表的長度不夠n,為什麼控制條件要大於1呢，因為我找的是被刪除節點的前一個節點
            return NULL;
        }
        while(fast)
        {
            fast=fast->next;
            slow=slow->next;
        }
        if(m == 1)
        {//刪除的節點是頭結點
            head = head->next;
            delete slow;
        }
        else
        {
            ListNode *toBedel = slow->next;
            slow->next=slow->next->next;
            delete toBedel;
        }
        return head;
    }
};