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

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第二章中“删除链表的中间节点和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

【实现】：

　　实现及测试代码：

  1 /*
  2  *文件名：lists_remove.cpp
  3  *作者：
  4  *摘要：实现删除链表的中间节点和 a/b 处的节点
  5  */
  6 #include <iostream>
  7 #include <math.h>
  8 
  9 using namespace std;
 10 
 11 struct Node
 12 {
 13     int value;
 14     Node *next;
 15 };
 16 
 17 //删除中间节点
 18 Node* removeMidNode(Node *head)
 19 {
 20     if(NULL == head || NULL == head->next)
 21         return head;
 22     
 23     if(NULL == head->next->next)
 24     {
 25         Node *ptr = head;
 26         head = head->next;
 27         delete ptr;
 28     }
 29     
 30     Node *pre = head;
 31     Node *cur = head->next->next;
 32     //找到待删除的中间节点的前一个（非双向链表）节点
 33     while(NULL != cur->next && NULL != cur->next->next)
 34     {    
 35         pre = pre->next;    
 36         cur = cur->next->next;
 37     }
 38     //将cur用作辅助指针
 39     cur = pre->next;
 40     pre->next = pre->next->next;
 41     delete cur;
 42     return head;
 43 }
 44 
 45 //进阶问题，删除 a/b 节点
 46 Node* removeByRatio(Node *head,int a,int b)
 47 {
 48     if(a < 1 || a > b)
 49         return head;
 50     int n = 0;
 51     Node *cur = head;
 52     
 53     while(NULL != cur)    //统计链表中节点个数->n
 54     {
 55         n++;
 56         cur = cur->next;
 57     }
 58     //由小数区间转化为整数，这是本题最有技巧的地方
 59     n = (int)ceil( ((double) (a*n)) / ((double) b) );
 60 
 61     if(1 == n)
 62     {
 63         cur  = head;
 64         head = head->next;
 65         delete cur;
 66     }
 67     
 68     if(1 < n)
 69     {
 70         cur = head;
 71         while( --n != 1)    //找到待删除节点的前一个节点
 72             cur = cur->next;
 73         Node *ptr = cur->next;
 74         cur->next = cur->next->next;
 75         delete ptr;
 76     }
 77     return head;
 78 }
 79 
 80 //打印链表内容
 81 void printLists(Node *head)
 82 {
 83     while(NULL != head)
 84     {
 85         cout << head->value << " " ;
 86         head = head->next;
 87     }
 88     cout << endl;
 89 }
 90 
 91 int main()
 92 {
 93     Node *head = NULL;
 94     Node *ptr = NULL;
 95     
 96     for(int i =0;i<10;i++)//构造链表
 97     {
 98         if(NULL == head)
 99         {    
100             head = new Node;
101             head->value = i;
102             head->next = NULL;
103             ptr = head;
104             continue;
105         }
106         ptr->next = new Node;
107         ptr = ptr->next;
108         ptr->value = i;
109         ptr->next = NULL;
110     }
111 
112     cout << "Before remove mid: " << endl;
113     printLists(head);
114     head = removeMidNode(head);
115     cout << "After remove mid: " << endl;
116     printLists(head);
117 
118     int a(2),b(5);
119     cout << "Before remove "<< a << "/" << b  << ": "<< endl;
120     printLists(head);
121     head = removeByRatio(head,a,b);
122     cout << "After remove "<< a << "/" << b  << ": "<< endl;
123     printLists(head);
124 
125     return 0;
126 }

View Code

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。