【说明】：
本文是左程云老师所著的《程序员面试代码指南》第二章中“删除链表的中间节点和a/b处节点”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】：
给定链表的头节点 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 节点问题：将小数区间转变为待删除节点的整数位置。
【编译环境】：
CentOS6.7（x86_64）
gcc 4.4.7
【实现】：
实现及测试代码：
/*
*文件名：lists_remove.cpp
*作者：
*摘要：实现删除链表的中间节点和 a/b 处的节点
*/
#include <iostream>
#include <math.h> using namespace std; struct Node
{
int value;
Node *next;
}; //删除中间节点
Node* removeMidNode(Node *head)
{
if(NULL == head || NULL == head->next)
return head; if(NULL == head->next->next)
{
Node *ptr = head;
head = head->next;
delete ptr;
} Node *pre = head;
Node *cur = head->next->next;
//找到待删除的中间节点的前一个（非双向链表）节点
while(NULL != cur->next && NULL != cur->next->next)
{
pre = pre->next;
cur = cur->next->next;
}
//将cur用作辅助指针
cur = pre->next;
pre->next = pre->next->next;
delete cur;
return head;
} //进阶问题，删除 a/b 节点
Node* removeByRatio(Node *head,int a,int b)
{
if(a < || a > b)
return head;
int n = ;
Node *cur = head; while(NULL != cur) //统计链表中节点个数->n
{
n++;
cur = cur->next;
}
//由小数区间转化为整数，这是本题最有技巧的地方
n = (int)ceil( ((double) (a*n)) / ((double) b) ); if( == n)
{
cur = head;
head = head->next;
delete cur;
} if( < n)
{
cur = head;
while( --n != ) //找到待删除节点的前一个节点
cur = cur->next;
Node *ptr = cur->next;
cur->next = cur->next->next;
delete ptr;
}
return head;
} //打印链表内容
void printLists(Node *head)
{
while(NULL != head)
{
cout << head->value << " " ;
head = head->next;
}
cout << endl;
} int main()
{
Node *head = NULL;
Node *ptr = NULL; for(int i =;i<;i++)//构造链表
{
if(NULL == head)
{
head = new Node;
head->value = i;
head->next = NULL;
ptr = head;
continue;
}
ptr->next = new Node;
ptr = ptr->next;
ptr->value = i;
ptr->next = NULL;
} cout << "Before remove mid: " << endl;
printLists(head);
head = removeMidNode(head);
cout << "After remove mid: " << endl;
printLists(head); int a(),b();
cout << "Before remove "<< a << "/" << b << ": "<< endl;
printLists(head);
head = removeByRatio(head,a,b);
cout << "After remove "<< a << "/" << b << ": "<< endl;
printLists(head); return ;
}
注：
转载请注明出处；
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。