原題鏈接Remove Nth Node From End of List

意思是給定一個鏈表，要求刪除倒數第n個節點，返回鏈表頭，復雜度在O(n)

---

思路就是找到倒數第n個和倒數第n+1個節點即可，僅僅遍歷一遍鏈表的話只需要記錄這兩個節點。
一個節點指向當前遍歷到的節點，記錄和鏈表頭的距離，如果到達n，開始記錄目標節點和目標節點的上一個節點。
以題目實例為例

(header) | (head) |NULL | 1 | 2 | 3 | 4 | 5 | NULL |tar_node | cur_node | | | | | |last_node| | | | | | |---------|------------- |-----------|-----------|-----------|-----------|---------- |tar_node | | cur_node | | | | |last_node| | | | | | |---------|------------- |-----------|-----------|-----------|-----------|---------- |tar_node | | | cur_node | | | |last_node| | | | | | -------------------------------------------------|-----------|-----------|---------- | | | | | | | |last_node| tar_node | | cur_node | | | -------------------------------------------------|-----------|-----------|---------- | | last_node| tar_node | | cur_node | | -------------------------------------------------|-----------|-----------|---------- | | | last_node| tar_node | | cur_node | -------------------------------------------------|-----------|-----------|---------- | | | | last_node| tar_node | | cur_node ------------------------------------------------------------------------------------

基本步驟就是這樣（-.-，竟然手動畫了個表格）
tar_node開始移動的時機是cur_node于tar_node的距離大于n，就需要將tar_node后移，始終保持這二者間距離小于等于n。在結束之后將last_node的next指向tar_node的next。
這里有個邊界條件問題，當要刪除的節點是鏈表頭時，也就是說tar_node是head，此時last_node是NULL，執行last_node->next = tar_node->next會出錯。
有一個小技巧，為鏈表手動增加一個節點header，另header->next = head，此時上面三個節點初始位置都是手動添加的這個節點header，也就是替代了NULL，這樣即使要刪除鏈表頭，那么last_node也會是header，不再是NULL。
代碼如下

/*** 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) {/* 手動添加一個節點，指向鏈表頭，初始三個指針都指向這個新添加的節點 */ListNode* header = new ListNode(-1);header->next = head;ListNode* cur_node = header;ListNode* tar_node = header;ListNode* tar_last_node = header;int node_cnt = 0;while(cur_node){cur_node = cur_node->next;/* 保證cur_node和tar_node的距離始終小于等于n */if(++node_cnt > n){tar_last_node = tar_node;tar_node = tar_node->next;node_cnt = n;}}/* 刪除tar_node */tar_last_node->next = tar_node->next;ListNode* ans = header->next;/* 刪除添加的頭部節點 */delete header;return ans;} };

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----删除链表倒数第n个节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。