笔试算法题（19）：判断两条单向链表的公共节点 & 字符集删除函数

出题：给定两个单向链表的头结点，判断其是否有公共节点并确定第一个公共节点的索引；

分析：

由于是单向链表，所以每个节点有且仅有一个后续节点，所以只可能是Y型交叉（每条链表中的某个节点同时指向一个公共节点，并共享后面的所有节点）。首先计算每条链表的长度，m和n（m>n）；
然后设定两个指针A和B分别指向两条链表头（A指向较长链表），让A先走（m-n）步，然后A和B同时前进，当（A==B）成立的时候A和B当前指向的节点就是第一个公共节点；

解题：

 1 struct Node {
 2         int v;
 3         Node *next;
 4 };
 5 
 6 Node* findFirstCommon(Node *first, Node *second) {
 7         /**
 8          * 首先计算first和second各自的长度
 9          * 当任一链表长度为0时返回NULL
10          * */
11         Node *firstT=first, *firstP=NULL;
12         Node *secondT=second, *secondP=NULL;
13         int firstL=0, secondL=0;
14         while(firstT!=NULL) {
15                 firstL++;
16                 firstP=firstT;
17                 firstT=firstT->next;
18         }
19         while(secondT!=NULL) {
20                 secondL++;
21                 secondP=secondT;
22                 secondT=secondT->next;
23         }
24         /**
25          * 判断是否存在公共节点，也就是长度不为0并且最后一个
26          * 节点相同
27          * */
28         if(firstL==0 || secondL==0)
29                 return NULL;
30         if(firstP!=secondP)
31                 return NULL;
32         /**
33          * 同步链条链表的指针，使得firstT和secondT指向的
34          * 位置距离链表最后一个节点有相同的距离
35          * */
36         int difference=0;
37         if(firstL>secondL) {
38                 difference=firstL-secondL;
39                 firstT=first;
40                 secondT=second;
41                 for(int i=0;i<difference;i++)
42                         firstT=firstT->next;
43         } else if(firstL<secondL) {
44                 difference=secondL-firstL;
45                 firstT=first;
46                 secondT=second;
47                 for(int i=0;i<difference;i++)
48                         secondT=secondT->next;
49         }
50         printf("%d, %d",firstT->v,secondT->v);
51         /**
52          * 同步指针之后，同时向前移动，firstT==secondT的时候
53          * 表示第一个公共节点，由于已经现在已经确定肯定有公共
54          * 节点，所以可以这样判断
55          * */
56         while(firstT!=NULL && secondT!=NULL) {
57                 if(firstT==secondT)
58                         break;
59                 firstT=firstT->next;
60                 secondT=secondT->next;
61         }
62         return firstT;
63 }

出题：实现字符集删除函数，要求在第一个字符串first中删除所有在第二个字符串second中出现的字符；

分析：

解法1：可以使用暴力解法，遍历first中每一个字符，并与second中的字符比较，如果有相同则删除，然后比较first中下一个字符，时间复杂度为O（mn）；
解法2：由于是判断某一个字符是否存在的情况，所以可以使用Hash Table，将first映射到256大小的HT中，然后将second也映射过去，一旦遇到已经存在的字符，则删除；最后遍历first并比较HT中的结果然后输出。此方法时间复杂度为O（N），但是需要使用额外内存保存最终结果，并不会改变原有的字符串；
解法3：由于解法2需要使用额外的空间保存字符串，当字符串较大的时候不可取；所以需要考虑如何快速的在原有字符串上进行字符删除，可以考虑两个指针 left和right，使用right对first字符串进行遍历并通过hashTable（仅仅映射second字符串）判断是否需要删除当前字符，如果需要进行删除则right指针直接跳过，如果不需要删除则将*left=*right，然后处理下一个字符，所以left指针记录了最终保存的字符串，这样可以在O（N）的时间内完成，并且不需要任何额外内存；

解题：

 1 void charSetDelete(char *first, char *second) {
 2         /**
 3          * 由于char集一般为256，所以初始化一个bool数组
 4          * 并且缺省所有的值都为false
 5          * */
 6         bool hashTable[256];
 7         for(int i=0;i<256;i++)
 8                 hashTable[i]=false;
 9         /**
10          * 首先映射first字符串，true表示需要输出
11          * 然后映射second字符串，false表示不需要输出
12          * */
13         char *firstT=first, *secondT=second;
14         while(*firstT != '') {
15                 hashTable[*firstT]=true;
16                 firstT++;
17         }
18         while(*secondT != '') {
19                 hashTable[*secondT]=false;
20                 secondT++;
21         }
22         /**
23          * 通过hashTable对应元素是true还是false进行
24          * 输出判断
25          * */
26         firstT=first;
27         printf("
");
28         while(*firstT != '') {
29                 if(hashTable[*firstT])
30                         printf("%c",*firstT);
31                 firstT++;
32         }
33         printf("
");
34 }
35 
36 void betterVersion(char *first, char *second) {
37         bool hashTable[256];
38         for(int i=0;i<256;i++)
39                 hashTable[i]=false;
40         /**
41          * hashTable用于记录second中指定需要
42          * 删除的字符集合
43          * */
44         char *secondT=second;
45         while(*secondT!='') {
46                 hashTable[*secondT]=true;
47                 secondT++;
48         }
49         /**
50          * 使用两个指针完成字符串的删除移动操作
51          * 仅当right索引的字符不需要删除的时候
52          * 才将其复制给left指向的位置
53          * */
54         char *left=first, *right=first;
55         while(*right!='') {
56                 if(!hashTable[*right]) {
57                         *left=*right;
58                         left++;
59                 }
60                 right++;
61         }
62         *left='';
63         char *temp=first;
64         while(*temp!='')
65                 printf("%c",*temp++);
66 }
67 
68 int main() {
69         char first[]="abcdefgghjjjj";
70         char second[]="agj";
71         charSetDelete(first, second);
72         betterVersion(first, second);
73         return 0;
74 }