查找单链表的倒数第k个值
刚开始，我想到的是一种笨方法，先遍历单链表，计算出单链表的长度len，然后再从头遍历单链表到第len-k个节点，那么这个节点既是单链表的倒数第k个节点。不过这种算法时间复杂度挺高的，还有一种更简单的方法，就是设置两个指针，分别指向单链表的头节点，然后让其中一个指针，先走k步，之后，再让两个指针同时走，直到第一个指针走到单链表尾节点结。
Java分词
Lucene，http://www.cnblogs.com/zuoxiaolong/p/lang2.html
php分词
一个专门的库 http://www.cnblogs.com/xshang/p/3603037.html
判断一个链表是不是循环链表
算法思想：在建立循环链表时设置两个指针，头指针和尾指针，head和tail,使tail->next=head,即让尾节点指向头节点，建立的时候采用尾插入法，每次让新节点先指向尾节点的下一个节点，然后让头节点的下一个节点指向新节点，然后让新节点赋值给头节点和尾节点。
判断是否是循环链表时，也设置两个指针，慢指针和快指针，让快指针比慢指针每次移动快两次。如果快指针追赶上慢指针，则为循环链表，否则不是循环链表，如果快指针或者慢指针指向NULL，则不是循环链表。
有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。
问题：
1、如何判断一个链表是不是这类链表？ 2、如果链表为存在环，如果找到环的入口点？
一、判断链表是否存在环，办法为：
设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定 相遇。(当然，fast先行头到尾部为NULL，则为无环链表)。
二、找到环的入口点：
当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则 fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：
2s = s + nr
s= nr
设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L – a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每 次各走一步，两个指针必定相遇，且相遇第一点为环入口点。
判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。
一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。
二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。
这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次 一步，相遇的第一点即为两个链表相交的第一个点
一个整型数组里除了一个或者两个或者三个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)
- 如果只有一个出现一次，考察到异或的性质，就是如果同一个数字和自己异或的活结果为零，那么循环遍历一遍数组，将数组中的元素全部做异或运算，那么出现两次的数字全部异或掉了，得到的结果就是只出现一次的那个数字。
- 如果有两个只出现一次的数字，设定为a,b。也是应用异或，但是数组元素全部异或的结果x=a^b，因为a,b是不相同的数字，因此x肯定不为0。对于x，从低位到高位开始，找到第一个bit位为1的位置设定为第m位，这个第m位的bit肯定来自a或者来自b，不可能同时a,b的第m位（从低到高位）都为1。这样，就可以根据这个第m位就可以把数组分为两个部分，一组为第m位为0，一组为第m位为1.这样，就把问题分解成了求两个数组中只出现一次的数字了。
- 考虑给定数组中有三个单独出现一次的数字，这个会比有两个的稍微复杂。分步分析，设定这三个数为a,b,c:
(1)将数组中的数字全部异或，得到的结果x=a^b^c，但是x不是a，b，c中的其中一个，假设x=a，那么b^c=0说明b=c，与题目给定的条件矛盾。
(2)设定f(n)可以像2中的那样，从低位开始，找到第一个bit为1的位置，f(x^a),f(x^b),f(x^c)得到的值肯定都不为0，因为x^a,x^b,x^c本身就不为0。f(x^a)^f(x^b)^f(x^c)结果不为0。因为f(x^a)^f(x^b)的结果中可能为0，也可能有两个bit为1。如果假设f(x^c)的结果bit为1的位置与f(x^a)^f(x^b)的其中一个重合，则f(x^a)^f(x^b)^f(x^c)结果中只有1个bit为1，如果不重合的话那么有3个bit位为1。
(3)这便可以推断出f(x^a)^f(x^b)^f(x^c)中至少有一个bit位为1。假设从低位到高位的第mbit位为1.那么可以得出结论x^a,x^b,x^c中有一个或者三个的第m位为1（不可能有两个，因为有两个的话，异或的结果就为0了）。
(4)证明，x^a,x^b,x^c中只有一个第m-bit位为1.假设他们的第m位都为1，那么x的第m位为0，但是x=a^b^c其第m位肯定为1，所以假设不成立。那么相反，假设x的第m位为1，a,b,c的第m位都为0，也不成立，因为x=a^b^c。所以综上所述x^a,x^b,x^c中只有一个第m位为1。那么这个问题就好办了。根据这个第m位找到第一个只出现一次的数字。
将给定的英文字符串进行反转
双指针，一个在最前面，一个在最后面，然后调换内容。
例如： I love programming。得到的结果是：.gnimmargorp evol I。下面给出核心代码：
#include<stdio.h> #include<string.h> void swap_string(char *p_start, char *p_end) { char temp; while(p_start <= p_end) { temp = *p_start; *p_start = *p_end; *p_end = temp; p_start++; p_end--; } } void main() { char str[] = "I love programming."; swap_string(str, str + strlen(str) - 1); printf("%s\n", str); }
给定一个字符串，例如：" test ** "，要求出去字母之外其他多余的字符
这也需要设定两个指针，一个慢指针和一个快指针，如果快指针指到的是字母，则赋值给慢指针，否则快指针继续前进，核心代码如下：
#include<stdio.h> #include<string.h> void trim_word(char *word) { char *p_slow = word; char *p_fast = word; while(*p_fast) { if(!(*p_fast >= 'a' && *p_fast <= 'z') && !(*p_fast >= 'A' && *p_fast <= 'Z')) { p_fast++; } else { *p_slow++ = *p_fast++; } } *p_slow = '\0'; } void main() { char word[] = " test ** "; trim_word(word); printf("%s\n", word); }
给定一个字符串，例如："abccba"，判断它是否是回文
可以应用数组解决，但是数组的索引速度没有指针的移动速度快，所以设定两个指针，一个指向字符串开始，一个指向字符串结尾，同步移动。核心代码如下：
#include<stdio.h> #include<string.h> int is_palindrome(char *str) { char *p_start = str; char *p_end = str + strlen(word) - 1; while(p_start < p_end) { if(*p_start != *p_end) { return 0; } p_start++; p_end--; } return 1; } void main() { char string[] = "abccba"; if(is_palindrome(string)) { printf("string is palindrome.\n"); } else { printf("string is not palindrome.\n"); } }
给定一个有序数组，然后给定一个数字m，在数组中找出两个数，使得这两个数的和与m相等
#include<stdio.h> #include<stdlib.h> void FindTwoNumbers(int a[], int n, int dest) { int *e, *f; e = a; f = a + n - 1; int sum; sum = *e + *f; while(sum != dest && e < f) { if(sum < dest) { sum = sum - *e + *(++e); } else { sum = sum - *f + *(--f); } } if(sum == dest) { printf("%d=%d+%d\n",dest,*e,*f); } else { printf("not find\n"); } } void main() { int num[] = {1, 2, 4, 7, 11, 15}; int temp = 9; FindTwoNumbers(num, sizeof(num)/sizeof(int), temp); }
字符串移位问题
就是字符串移位问题，这个也用到的双指针，假设给定字符串“abcdefg”，让字符串向左移动三位,得到的结果是：“defgabc”,这个怎么做呢，首先找到分界点，将字符串分为两部分，很自然的分界点应该和移动位数有关，故将字符串分为:abc,defg两部分，先分别将两部分翻转成：cbagfed，然后再将整个字符串翻转：defgabc。
输入两个字符串，从第一字符串中删除第二个字符串中所有的字符
例如，输入”They are students.”和"aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。这个题的思路其实也可以用双指针来完成。首先我们还得设定一个hash表，来记录在第二个字符串中有哪些字母出现。当hash值等于1的时候表示在第二个字符串，也就是要除去的字符串中出现，等于0的时候表示不出现。然后遍历第一个字符串，设定两个指针，一个p_slow, 一个p_fast，如果某个单词的hash值为1，说明要从原始字符串中除去这个单词，那么p_fast++。这个讲解起来有点不清晰，直接给出代码吧。
#include<stdio.h> #include<stdlib.h> #include<string.h> void trim_string(char *string, char *trim_str) { int hash[256] = {0}; int len_trim = strlen(trim_str); char *p_slow = string; char *p_fast = string; int i; for(i = 0; i < len_trim; i++) { hash[trim_str[i]]++; } while(*p_fast) { if(hash[*p_fast] > 0) { p_fast++; } else { *p_slow++ = *p_fast++; } } *p_slow = '\0'; } void main() { char string[] = "They are students."; char trim[] = "aeiou"; trim_string(string, trim); printf("%s\n", string); }
在O（n）时间内删除字符串中重复的字符，不使用Hash
位图，bitmap：
#include<stdio.h> #include<string.h> void remove_duplicate(char *str) {// assume all characters are little char *p_slow = str; char *p_fast = str; int flag = 0; int value; int bits; while(*p_fast) { value = 1; bits = *p_fast - 'a'; value = (value << bits); if((flag & value) == value) { p_fast++; } else { *p_slow++ = *p_fast++; flag |= value; } } *p_slow = '\0'; } void main() { char str[] = "abcddbcdefghijm"; remove_duplicate(str); printf("%s\n", str); getchar(); }
反转句子中单词的顺序，忽略标点符号的处理
反转句子中单词的顺序，即把一个英文句子的单词顺序倒转，忽略标点符号的处理,例如： I love linux programming. 操作之后结果： .programming linux love I。也需要设定双指针，这个情况和题目1有相似之处，但是又不完全的相同，需要在反转的过程中做一些判断，下面给出代码：
#include<stdio.h> #include<string.h> void swap_block(char *start, char *end) { char temp; while(start < end) { temp = *start; *start = *end; *end = temp; start++; end--; } } void reverse_sentence(char *str) { char *p_slow = NULL; char *p_fast = NULL; swap_block(str, str + strlen(str) - 1); p_slow = str; p_fast = str; while(*p_fast) { if((*p_fast >= 'a' && *p_fast <= 'z') || (*p_fast >= 'A' && *p_fast <= 'Z')) { p_fast++; } else { swap_block(p_slow, p_fast - 1); while(!(*p_fast >= 'a' && *p_fast <= 'z') && !(*p_fast >= 'A' && *p_fast <= 'Z')) { p_fast++;//跳过多余的空格 } p_slow = p_fast; } } } void main() { char str[] = "I love linux programming."; reverse_sentence(str); printf("%s\n", str); getchar(); }
