"Coding Interview Guide" -- 删除链表的中间节点和a/b处的节点

【题目】

　　给定链表的头节点head，实现删除链表的中间节点的函数

　　例如：1，不删除任何节点；

1->2，删除节点1；

　　　　 1->2->3，删除节点2；

　　　　 1->2->3->4，删除节点2；

　　　　 1->2->3->4->5，删除节点3；

 1     public Node removeMidNode(Node head)
 2     {
 3         if(head == null || head.next == null)
 4         {
 5             return null;
 6         }
 7 
 8         if(head.next.next == null)
 9         {
10             return head.next;
11         }
12 
13         Node pre = head;
14         Node cur = head.next.next;
15         while(cur.next != null && cur.next.next != null)
16         {
17             pre = pre.next;
18             cur = cur.next.next;
19         }
20         pre.next = pre.next.next;
21         return head;
22     }

【总结】　

 1 N：链表长度
 2 #1 
 3     pre = head;
 4     cur = head;
 5     当N为偶数时，找到的节点为N/2；
 6     当N为奇数时，找到的节点为N/2 + 1;
 7 
 8 #2
 9     pre = head;
10     cur = head.next;
11     当N为偶数时，找到的节点为N/2；
12     当N为奇数时，找到的节点为N/2；
13 
14 #3
15     pre = head;
16     cur = head.next.next;
17     当N为偶数时，找到的节点为N/2 - 1;
18     当N为奇数时，找到的节点为N/2；(#3找到的是#1找到的节点的前一个节点)

【题目】

　　给定链表的头节点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，不删除任何节点

【分析】

　　(int) Math.ceil((((double) (a * n)) / (double) b)的值即为该删除的节点是链表中的第几个节点

 1     public Node removeByRatio(Node head, int a, int b)
 2     {
 3         if(a < 1 || a > b)
 4         {
 5             return head;
 6         }
 7 
 8         int n = 0; 
 9         Node cur = head;
10         while(cur != null)
11         {
12             n++;
13             cur = cur.next;
14         }
15 
16         n = (int) Math.ceil(((double) (a * n)) / (double) b);  // 确定删除的是第n个节点
17         if(n == 1)
18         {
19             head = head.next;
20         }
21         if(n > 1)
22         {
23             cur = head;
24             while(--n > 1)
25             {
26                 cur = cur.next;
27             }
28             cur.next = cur.next.next;
29         }
30         return head;
31     }

【总结】

 1 java的Math类中四种静态取整方法：
 2 #1
 3     public static double ceil(double);  // 向上取整
 4 
 5 #2
 6     public static double floor(double);    // 向下取整
 7 
 8 #3
 9     public static double round(double);     // 四舍五入
10 
11 #4
12     public static double rint(double);  // 返回最接近参数的整数，如果有两个数都接近参数，则返回其中的偶数值

来源：左程云老师《程序员代码面试指南》