题目
给定链表表的头节点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，不除任何节点。
思路
先来分析原问题，如果链表为空或者长度为1，不需要调整，则直接返回;如果链表的长度为2，将头节点除即可；当链表长度到达3，应该删除第2个节点;当链表长度为4，应该除第2个节点；当链表长度为5，应该删除第3个节点……也就是链表长度每增加2 (3,5,7……)。要删除的节点就后移一个节点。删除节点的问题在之前的题目中我们已经讨论过，如果要删除个节点，则需要找到待删除节点的前一个节点。
具体过程请参看如下代码中的 removemidnode方法接下来时论进阶问题，首先需要解决的问题是，如何根链表的长度n，以及a与b的值决定该删除的节点是那一个节点呢? 根据如下方法: 先计算 double r
= ((double)(a * n)) / ((double)b) 的值，然后 r 向上取整之后的整数值，代表该删除的节点是第几个节点。
下面几个例子来验证一下。
如果表长度为7，a＝ 5，b ＝ 7，
r ＝ (7 * 5) / 7＝ 5.0，向上取整后为5，所以应该删除第5个节点。
如果链表长度为7，a = 5，b＝ 6。
r ＝ (7 * 5) / 6＝5.8333…，向上取后为6，所以应该除第6个节点。
如果链表长度为7，a＝1，b＝6
r＝，(7 * 1) / 6 = 1.6666…，向上取整后为2，所以应该别第2个节点。
知道该除第几个节点之后，接下来需要找到删除节点的前一个节点即可，具体过程参
看如下代码中的 removebyratio方法
代码演示
package com.itz.zcy.listQuestion;
/**
* 给定链表表的头节点head，实现别删除链表的中间节点的函数
*/
public class RemoveListCentreNodeAndabNode {
/**
* 节点
*/
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
/**
* 给定链表表的头节点head，实现别删除链表的中间节点的函数
*
* @param head
* @return
*/
public static Node removeMidNode(Node head) {
// 异常判定
if (head == null || head.next == null) {
return head;
}
// 土豪只有一个节点直接返回
if (head.next == null) {
return head.next;
}
Node pre = head;
Node cur = head.next.next;
// 当下一个和下一个的下一个不为空时候，指向下一个和下一个的下一个
while (cur.next != null && cur.next.next != null) {
pre = pre.next;
cur = cur.next.next;
}
// 删除节点
pre.next = pre.next.next;
return head;
}
/**
* 进阶: 给定链表的头节点head、整数a和b，实现删除位于a/b处节点的函数
*
* @param head
* @param a
* @param b
* @return
*/
public static Node removeByRatio(Node head, int a, int b) {
if (a < 1 || a > b) {
return head;
}
int n = 0;
Node cur = head;
// 求出链表的长度
while (cur != null) {
n++;
cur = cur.next;
}
// 计算需要删除的节点
n = (int) Math.ceil(((double) (a * n)) / (double) b);
// 等于1是直接删除第一个节点
if (n == 1) {
head = head.next;
}
// 大于1的时候
if (n > 1) {
cur = head;
while (--n != 1) {
cur = cur.next;
}
cur.next = cur.next.next;
}
return head;
}
public static void main(String[] args) {
Node node1 = new Node(1);
node1.next = new Node(2);
node1.next.next = new Node(3);
node1.next.next.next = new Node(4);
node1.next.next.next.next = new Node(5);
node1.next.next.next.next.next = new Node(6);
node1.next.next.next.next.next.next = new Node(7);
Node head1 = removeMidNode(node1);
while (true){
if (head1!=null){
if (head1.next == null){
System.out.print(head1.value);
}else {
System.out.print(head1.value+" → ");
}
}else {
break;
}
head1 = head1.next;
}
System.out.println();
Node node2 = new Node(1);
node2.next = new Node(2);
node2.next.next = new Node(3);
node2.next.next.next = new Node(4);
node2.next.next.next.next = new Node(5);
node2.next.next.next.next.next = new Node(6);
node2.next.next.next.next.next.next = new Node(7);
Node head2 = removeByRatio(node2,2,3);
while (true){
if (head2!=null){
if (head2.next == null){
System.out.print(head2.value);
}else {
System.out.print(head2.value+" → ");
}
}else {
break;
}
head2 = head2.next;
}
// 1 → 2 → 3 → 5 → 6 → 7
// 1 → 2 → 3 → 4 → 6 → 7
}
}
总结
该题目比较简单；时间复杂度是O(n),空间复杂度O(1)。
文献：左程云著 《程序员代码面试指南IT名企算法与数据结构题目最优解》（第二版）
版权声明：此文版权归作者所有！
