删除链表的中间结点和a/b处的结点

题目：给定链表的head结点，删除一个链表的中间结点，当链表只有一个结点的时候或者head结点为空的时候返回head，当链表有两个结点的时候删除第一个节点，当链表有三个结点的时候删除第二个结点，当链表有四个结点的时候删除第二个结点，当链表有五个结点的时候删除第三个结点……

分析：一个链表长度每增加二，要删除的结点就后移一个结点，要删除一个结点需要知道它的前一个结点。

// 删除链表中间结点
Node* removeMidNode(Node* head) {
    // 如果链表的为空，且链表只有一个结点，则不需要删除
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // 如果链表只有两个结点，则删除第一个结点
    if (head->next->next == NULL) {
        return head->next;
    }

    // 如果链表有两个以上的结点，则cur每走两步，pre走一步
    Node* pre = head;               // 中间结点的前一个结点从head开始
    Node* cur = head->next->next;   // cur结点从第三个结点开始
    while (cur->next && cur->next->next) {  // cur结点每走两步，中间结点走一步（即pre结点走一步）
        pre = pre->next;
        cur = cur->next->next;
    }
    
    pre->next = pre->next->next;

    return head;
}

进阶

题目：给两个整数a，b，实现删除a/b处节点的函数。r = a/b（r<=1），若r=0，不删除；其他r的值向上取整，比如r在范围(2/5,3/5]中，取3，删除第三个节点。

首先涉及到一个求链表长度，一次遍历，然后是求删第几个，涉及到一个向上取整的运算。最后依旧是注意要取得r前一个的元素，才能删除r。

#include <cmath>
// 删除a/b处的结点
Node* removeNodeRatio(Node* head, int a, int b) {
    if (head == NULL || a > b) {
        return head;
    }

    // 统计链表结点的个数
    int count = 0;
    Node* n = head;
    while (n) {
        count++;
        n = n->next;
    }

    // 计算需要删除的结点的位置
    double pos = double(a) * double(count) / double(b);
    int pos_node = ceil(pos);   // pos向上取整

    // 查找需要删除结点的前一个结点，删除需要删除的结点
    // 如果需要删除的结点为头结点，则返回head->next
    if (pos_node == 1) {
        head = head->next;
    }

    if (pos_node > 1) {
        n = head;
        while (--pos_node != 1) {   // 寻找待删除结点的前一个结点
            n = n->next;
        }

        n->next = n->next->next;
    }

    return head;
}