題目：給定鏈表的head結(jié)點(diǎn)，刪除一個(gè)鏈表的中間結(jié)點(diǎn)匹层，當(dāng)鏈表只有一個(gè)結(jié)點(diǎn)的時(shí)候或者h(yuǎn)ead結(jié)點(diǎn)為空的時(shí)候返回head绷耍，當(dāng)鏈表有兩個(gè)結(jié)點(diǎn)的時(shí)候刪除第一個(gè)節(jié)點(diǎn)魏保，當(dāng)鏈表有三個(gè)結(jié)點(diǎn)的時(shí)候刪除第二個(gè)結(jié)點(diǎn)，當(dāng)鏈表有四個(gè)結(jié)點(diǎn)的時(shí)候刪除第二個(gè)結(jié)點(diǎn)漂坏，當(dāng)鏈表有五個(gè)結(jié)點(diǎn)的時(shí)候刪除第三個(gè)結(jié)點(diǎn)……
分析：一個(gè)鏈表長(zhǎng)度每增加二景埃，要?jiǎng)h除的結(jié)點(diǎn)就后移一個(gè)結(jié)點(diǎn)，要?jiǎng)h除一個(gè)結(jié)點(diǎn)需要知道它的前一個(gè)結(jié)點(diǎn)顶别。
// 刪除鏈表中間結(jié)點(diǎn)
Node* removeMidNode(Node* head) {
// 如果鏈表的為空谷徙，且鏈表只有一個(gè)結(jié)點(diǎn)，則不需要?jiǎng)h除
if (head == NULL || head->next == NULL) {
return head;
}
// 如果鏈表只有兩個(gè)結(jié)點(diǎn)驯绎，則刪除第一個(gè)結(jié)點(diǎn)
if (head->next->next == NULL) {
return head->next;
}
// 如果鏈表有兩個(gè)以上的結(jié)點(diǎn)完慧，則cur每走兩步，pre走一步
Node* pre = head; // 中間結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)從head開始
Node* cur = head->next->next; // cur結(jié)點(diǎn)從第三個(gè)結(jié)點(diǎn)開始
while (cur->next && cur->next->next) { // cur結(jié)點(diǎn)每走兩步剩失，中間結(jié)點(diǎn)走一步（即pre結(jié)點(diǎn)走一步）
pre = pre->next;
cur = cur->next->next;
}
pre->next = pre->next->next;
return head;
}
進(jìn)階
題目：給兩個(gè)整數(shù)a屈尼，b，實(shí)現(xiàn)刪除a/b處節(jié)點(diǎn)的函數(shù)拴孤。r = a/b（r<=1）脾歧，若r=0，不刪除演熟；其他r的值向上取整鞭执，比如r在范圍(2/5,3/5]中，取3绽媒，刪除第三個(gè)節(jié)點(diǎn)蚕冬。
首先涉及到一個(gè)求鏈表長(zhǎng)度，一次遍歷是辕，然后是求刪第幾個(gè)囤热，涉及到一個(gè)向上取整的運(yùn)算。最后依舊是注意要取得r前一個(gè)的元素获三，才能刪除r旁蔼。
#include <cmath>
// 刪除a/b處的結(jié)點(diǎn)
Node* removeNodeRatio(Node* head, int a, int b) {
if (head == NULL || a > b) {
return head;
}
// 統(tǒng)計(jì)鏈表結(jié)點(diǎn)的個(gè)數(shù)
int count = 0;
Node* n = head;
while (n) {
count++;
n = n->next;
}
// 計(jì)算需要?jiǎng)h除的結(jié)點(diǎn)的位置
double pos = double(a) * double(count) / double(b);
int pos_node = ceil(pos); // pos向上取整
// 查找需要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，刪除需要?jiǎng)h除的結(jié)點(diǎn)
// 如果需要?jiǎng)h除的結(jié)點(diǎn)為頭結(jié)點(diǎn)疙教，則返回head->next
if (pos_node == 1) {
head = head->next;
}
if (pos_node > 1) {
n = head;
while (--pos_node != 1) { // 尋找待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
n = n->next;
}
n->next = n->next->next;
}
return head;
}
