程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 筆試題32. LeetCode OJ (19)

筆試題32. LeetCode OJ (19)

編輯:關於C++

\

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

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

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

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

 

int m=K+1;
while(m && fast)
{
	fast = fast->next;
	--m;
}
最後判斷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;
    }
};
最後我還是附上這個吧

 

\

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved