題意：
給定一個鏈表，洗掉鏈表的倒數第 n 個節點，并且回傳鏈表的頭結點，
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2. 當洗掉了倒數第二個節點后，鏈表變為 1->2->3->5.
說明：
給定的 n 保證是有效的，
演算法：
定義兩個指標fast，slow，其中fast指標先走n步，因為題目保證給定的n是有效的，所以如果fast走n步后值為NULL，則洗掉頭結點；
否則兩個指標開始一起走，直到fast指向鏈表最后一個節點，此時slow所指節點為應該洗掉節點的前一個節點，
代碼：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* removeNthFromEnd(ListNode* head, int n) { 12 ListNode *fast = head; 13 ListNode *slow = head; 14 ListNode *temp = NULL; 15 while (n--) 16 fast = fast->next; 17 if (fast == NULL) 18 { 19 temp = head->next; 20 delete head; 21 return temp; 22 } 23 while (fast->next != NULL) 24 { 25 fast = fast->next; 26 slow = slow->next; 27 } 28 temp = slow->next; 29 slow->next = temp->next; 30 delete temp; 31 return head; 32 } 33 };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205854.html
標籤：其他
上一篇：詳細講解Codeforces Round #624 (Div. 3) E. Construct the Binary Tree（構造二叉樹）