面试经典问题：
“逆置一个单链表”
链表结构为：
1 typedef struct node
2 {
3 int data;
4 struct node *next;
5 } NODE;
由于题目限制比较少，所以就需要仔细考虑，链表是否有环？如果链表有
小环那么链表将不可逆置，因为环的入口节点有两个前驱节点。所有首先应该判断链表是否有小环，如果没有小环才能对链表进行逆置。而如何判断链表是否有环？
一种方法是用一个指针遍历链表，每遍历一个节点便对节点做标记，如果节点走到NULL，则说明没有环，如果遇到了已经做过标记的节点，则说明有环，且这个做标记的节点就是入口。但是
如果不允许对节点做标记该怎么办呢？另外一种方法是对每个节点的地址做hash，每次访问一个节点的时候都查看hash表，如果该节点的地址不在hash表中，则说明该节点未被访问，直到遇到NULL或者遇到某个节点在hash表中有记录，则该节点则是环的入口。该算法同样有很大的弊病，需要大量内存，因为节点的地址是32位的。下面提供
第三种方法：采用两个指针（假设为p1,p2），初始情况下都指向链表头，之后p2每次走2步，p1每次走1步，当p1和p2相交的时候则说明有环，否则当p2走到NULL的时候则说明无环，证明也比较简单。那么如何找到环的入口点呢？这里提供一种方法：当确定有环后，p2在相交处，p1重新指向链表开头，然后每次两个指针都各走一步，这样两个指针再次相遇的时候便是环的入口处。证明如下：
假设从链表头到环的入口长度为l，环的周长为r，p1和p2相遇的点距离环入口为x
则我们有以下结论：
1、第一次相交的时候p1还没有走完整条链表，而p2则在链表的环内转了n圈
2、第一次相交的时候p2走的距离是p1的两倍，因为p2每次走两步而p1每次走一步
这样我们就得到如下公式：
2(x + l) = l + x + nr
则可以得到l = nr - x
这样我们将p1重新放到链表头开始走，那么当p1节点走了l距离的时候，可以知道p2也走了l距离，而l = nr - x，所以p2走了nr - x，而p2从相交点开始走的，该点距离环入口处为x，这样可以知道当p2走了nr - x步后正好就到了环的入口，而p1此时也正在环的入口，可以知道p1和p2正好相遇，证毕。
下面一段代码是用来判断链表是否有环的，包括大环和小环：
1 node *list_isloop(node *head) {
2 if (head == NULL) return head;
3 node *p1 = head, *p2 = head;
4 do {
5 p2 = p2->next;
6 if (p2 == NULL || p2 == head) return p2;
7 p2 = p2->next;
8 if (p2 == NULL || p2 == head) return p2;
9 p1 = p1->next;
10 } while (p1 != p2);
11 p1 = head;
12 while (p1 != p2) { p1 = p1->next; p2 = p2->next; }
13 return p2;
14 }
其实对于单链表的操作，绝大部分都需要先判断链表是否为空，然后判断链表是否呦环，有大环和有小环在有写问题的处理方式未必一样，比如对于链表逆置，链表为空、或者链表有大环，链表都可以正常被逆置，而如果是有小环的链表，则链表不可被逆置。
下面看链表逆置的代码，其中调用了上面判断链表是否有环的函数：
1 node *list_reverse(node *head) {
2 if (head == NULL || head->next == NULL) return head;
3 node *entry = list_isloop(head);
4 if (entry != NULL && entry != head) return NULL;
5 node *p1 = head, *p2 = p1->next, *p3 = p2->next;
6 p1->next = NULL;
7 while (p3 && p3 != head) {
8 p2->next = p1;
9 p1 = p2;
10 p2 = p3;
11 p3 = p3->next;
12 }
13 p2->next = p1;
14 return p2;
15 }
下面一段代码是用来对单链表测长的，也许要对单链表判断是否有环：
1 int list_len(node *head) {
2 int len = 0;
3 node *p = head, *entry = NULL;
4 if (head == NULL) return 0;
5 entry = list_isloop(head);
6 while (p != entry) { ++len; p = p->next; }
7 if (entry != NULL)
8 do { ++len; p = p->next; } while (p != entry);
9 return len;
10 }
而下面一段代码是用来判断两个单链表是否相交的，该问题有点复杂：
首先，如果其中任意一条链表为空，则不可能相交
其次，如果两个链表都没有环，则判断链表的尾元素是否相同
再次，如果两个链表一个呦环，一个无环，则不可能相交
最后，如果两个链表均有环，则从其中一个入口处开始走一圈，如果中间和另一环的入口相遇则说明两链表相交
1 int list_intersecting(node *head1, node *head2) {
2 if (head1 == NULL || head2 == NULL) return 0;
3 node *entry1 = list_isloop(head1);
4 node *entry2 = list_isloop(head2);
5 //两个链表都没有环
6 if (entry1 == NULL && entry2 == NULL) {
7 while (head1->next != NULL) head1 = head1->next;
8 while (head2->next != NULL) head2 = head2->next;
9 if (head1 == head2) return 1;
10 return 0;
11 }
12 //两个链表都有环
13 else if (entry1 != NULL && entry2 != NULL) {
14 node *tmp = entry1;
15 while (tmp->next != entry1) {
16 if (tmp == entry2) return 1;
17 tmp = tmp->next;
18 }
19 if (tmp == entry2) return 1;
20 }
21 //一个有环一个无环
22 return 0;
23 }
下面是合并两个有序链表，该问题也需要考虑全面，既然有序，则不需要考虑是否有环，但是两个链表是否都是递增或者递减则需要考虑，我们在此不判断两个链表一个一个递增一个递减的情况。下面代码第三个参数代表链表单调性，flag = 0代表递增，flag != 0代表递减：
1 node *list_merge(node *head1, node *head2, int flag) {
2 if (head1 == NULL) return head2;
3 if (head2 == NULL) return head1;
4 flag = !!flag;
5 node *head = NULL;
6 if (flag == 0) {
7 if (head1->data < head2->data) {
8 head = head1;
9 head->next = list_merge(head1->next, head2, flag);
10 }
11 else {
12 head = head2;
13 head->next = list_merge(head1, head2->next, flag);
14 }
15 }
16 else {
17 if (head1->data > head2->data) {
18 head = head1;
19 head->next = list_merge(head1->next, head2, flag);
20 }
21 else {
22 head = head2;
23 head->next = list_merge(head1, head2->next, flag);
24 }
25 return head;
26 }
27 }
对于将链表排序也有一个非常巧妙的地方，我们知道普通数组排序一般采用快排、堆排或者归并排序，而在链表上却不那么容易，因为链表不能直接用索引来寻址，而是采用指针地址索引，所以快排、堆排都失去了优势，但是归并排序却如鱼得水，而且在数组归并排序当中被诟病的空间复杂度O(n)在链表排序当中也降为O(1)。这里面还用到了一个小技巧，就是如何找到链表的中间元素，这里采用两个指针一快一慢的方法：
1 node *list_sort(node *head, int flag) {
2 if (head == NULL || head->next == NULL) return head;
3 flag = !!flag;
4 node *p1 = head, *p2 = head;
5 while (p2 != NULL) {
6 if ((p2 = p2->next) == NULL) break;
7 if ((p2 = p2->next) == NULL) break;
8 p1 = p1->next;
9 }
10 p2 = p1->next;
11 p1->next = NULL;
12 p1 = list_sort(head, flag);
13 p2 = list_sort(p2, flag);
14 return list_merge(p1, p2, flag);
15 }
找到无环链表倒数第k个节点，该问题比较简单，只需要先设一个指针p2预先走k步，然后再让p2每次走一步，同时在链表开头也有一指针p1每次走一步，这样，当p2走到尾部的时候p1则恰好是倒数第k个节点：
1 node *list_ktailed(node *head, int k) {
2 if (k < 0) return NULL;
3 int i = 0;
4 node *p1 = head, *p2 = head;
5 for (; i < k; ++i) {
6 if (p2 == NULL) return NULL;
7 p2 = p2->next;
8 }
9 while (p2 != NULL) { p2 = p2->next; p1 = p1->next; }
10 return p1;
11 }
关于链表问题暂时写到此。