【题目】
给定链表的头节点head，实现删除链表的中间节点的函数。例如：不删除任何节点；1->2，删除节点1；1->2->3，删除节点2；1->2->3->4，删除节点2；1->2->3->4->5，删除节点3；进阶：给定链表的头节点head、整数a和b，实现删除位于a / b处节点的函数。例如：链表：1->2->3->4->5，假设a / b的值为r。如果r等于0，不删除任何节点；如果r在区间（0，1 / 5]上，删除节点1；如果r在区间（1 / 5，2 / 5]上，删除节点2；如果r在区间（2 / 5，3 / 5]上，删除节点3；如果r在区间（3 / 5，4 / 5]上，删除节点4；如果r在区间（4 / 5，1]上，删除节点5；如果r大于1，不删除任何节点。【题解】原题：使用快慢指针，当快指针到达链表尾部，则慢指针就是处于中间位置进阶：使用快慢指针求出链表长度，然后去确定a/b的位置
1 #include2 3 using namespace std; 4 5 struct Node 6 { 7 int val; 8 Node* next; 9 Node(int a = 0) :val(a), next(nullptr) {}10 };11 12 Node* deleteMid(Node* head)13 {14 if (head == nullptr || head->next == nullptr)15 return head;16 if (head->next->next == nullptr)17 return head->next;18 Node* p = head;19 Node* q = head->next->next;20 while (q && q->next)21 {22 p = p->next;23 q = q->next->next;24 }25 p->next = p->next->next;26 return head;27 }28 29 Node* deleteA_B(Node* head, int a, int b)30 {31 32 if (head == nullptr || head->next == nullptr)33 return head;34 35 //使用双向链表求出链表长度36 int n = 0;37 Node* p = head;38 Node* q = head;39 while (q->next && q->next->next)40 {41 n++;42 p = p->next;43 q = q->next->next;44 }45 if (q->next == nullptr)46 n = 2 * n;47 else48 n = 2 * n + 1;49 int k = (double)a / (double)b * double(n) + 0.5;//向上取整50 p = head;51 while (--k)52 {53 p = p->next;54 }55 p->next = p->next->next;56 return head;57 }58 59 template 60 void printList(T head)61 {62 T p = head->next;63 while (p)64 {65 cout << p->val << "->";66 p = p->next;67 }68 cout << endl;69 }70 71 int main()72 {73 Node* head = new Node();74 Node* p = head;75 for (int i = 1; i < 6; ++i)76 {77 Node* q = new Node(i);78 p->next = q;79 p = q;80 }81 //p = head;82 //printList(p);83 //p = head;84 //p = deleteMid(p);85 //printList(p);86 //p = head;87 //p = deleteA_B(p, 1, 5);88 //printList(p);89 p = head;90 p = deleteA_B(p, 2, 5);91 printList(p);92 93 return 0;94 }