编程 单向链表特殊操作
扩展问题1：查找单向链表中的倒数第k个节点。
思路：按照遍历查找链表的常用模式，可能会马上想到一种简单的方法就是：先遍历链表，看一下链表中有多少个节点。假设链表中有n个节点，那么要找倒数第k个，也就是正数n-k+1个了。接下来，只要指针从头向后走n-k步就可了。这种方法大约要执行2n-k次。
那么，有没有比上面的方法更高效的方法呢？把思维打开，不要固定在遍历链表的时候只能用有一个指针的思维定式上。我们可以尝试用多个指针以不同的次序开始遍历链表。
对于，这个问题，我们就可以设置两个指针，一个指针先在链表上走K步，然后另一个指针从链表头开始和前一个指针一起向后走，这样当第一个指针到达链表尾部时候，第二个指针就会在第一个指针前面k个结点处。这时就找到了倒数第K个节点，算法执行的次数为n 次,比上一个方法减少了一些步,如图4。
图4 查找倒数第k个节点
代码实现：
gleList* returnNodeFromBack(SingleList* head,int k)
//返回链表中的倒数第K节点的指针//输入参数：单链表的头指针，要查找的节点的倒数位置//输出参数：无//返回值：成功返回节点指针，失败返回NULLSingleList* returnNodeFromBack(SingleList* head,int k){ SingleList *firstPtr,*secondPtr; int count = 0; firstPtr = secondPtr = head; while((firstPtr)&&(count < k)) { firstPtr = firstPtr->next; count++; } if(count < k) { return NULL; } while(firstPtr) { firstPtr = firstPtr->next; secondPtr = secondPtr->next; } return secondPtr;}扩展问题2：查找单向链表中的中间节点，当节点个数为偶数时返回中间两个元素中的前者（后者）
思路：类似于第一个扩展问题，对于查找中间元素，我们首先也可以利用先遍布链表看一看总共有多少个节点，然后再走节点总个数的一半即可找到中间元素。显然，这种方法也是要遍历两次链表。
那么，能不能借鉴上面的改进方法再来改进一下这个问题呢。当然可以，在此问题中依然使用两个遍历指针。让第一个指针每次走两步，第二个指针每次走一步，这样因为第一个指针经过的节点数是第二指针的两倍，所以当第一个指针到达中点时，第二个指针正好处于链表的中间位置。
代码实现：
SingleList* returnMidNode(SingleList* head)
//返回链表的中间节点//输入参数：单链表的头指针//输出参数：无//返回值：中间节点的指针或NULLSingleList* returnMidNode(SingleList* head){ SingleList *firstPtr,*secondPtr; firstPtr = secondPtr = head; //链表中没有节点或只有一个节点 if((firstPtr == NULL) || (firstPtr->next == NULL)) { return firstPtr; } //while((firstPtr)&&(firstPtr->next)) //偶数个数时返回中间两个索引较大者 while((firstPtr->next)&&(firstPtr->next->next))//偶数个数时返回中间两个索引较小者 { firstPtr = firstPtr->next->next; secondPtr = secondPtr->next; } return secondPtr;}
扩展问题：返回两个链表的第一个交点?
仔细阅读上一个问题的思路，可发现思路中第一种解决方法就可以解决这个问题。但其时间的复杂度为O（n2）。那么能不能仿照第二种方法一样来提高算法的效率呢？答案，当然是可以。
分析两个相交链表的性质可知，如果相交，则交点之后的链表节点同时属于这两个链表。由此可以推断出，交点之后每条链表上节点的个数肯定是相同的。因此，如果两条链表节点的个数分别为len1和len2(len1>len2)，那么他们的第一个交点在第一条链表上肯定是第(len1-len2)个节点之后的某个节点。
总结上面的分析，我们得出一算法：
（1）先分别遍历一遍两条链表，求出两链表各自的节点个数len1和len2。
（2）让节点多的链表先走|len1-len2|
（3）两条链表同时向后步进，并判断节点是否相同。第一个相同点就是第一个交点。
代码实现：
view sourceprint?01 //求两条单向链表的第一个交点
02 //输入参数：两个单链表的头指针
03 //输出参数：无
04 //返回值：相交返回第一个交点指针,不相交返回NULL
05 SingleList* FirstIntersectNode(SingleList *head1,SingleList *head2)
06 {
07 SingleList *firstPtr = head1,*secondPtr = head2;
08 int len1 = 0,len2 = 0;
09
10 //循环遍历第一个链表
11 while(firstPtr)
12 {
13 firstPtr = firstPtr->next;
14 len1++;
15 }
16
17 //循环遍历第二个链表
18 while(secondPtr)
19 {
20 secondPtr = secondPtr->next;
21 len2++;
22 }
23
24 firstPtr = head1;
25 secondPtr = head2;
26
27 //让指向较长链表的指针，先走出长出的几步
28 if(len1 > len2)
29 {
30 for(int i=0; i < (len1-len2);i++)
31 {
32 firstPtr = firstPtr->next;
33 }
34 }
35 else
36 {
37 for(int i=0; i < (len2-len1);i++)
38 {
39 secondPtr = secondPtr->next;
40 }
41 }
42 while(firstPtr&&secondPtr)
43 {
44 if(firstPtr == secondPtr)
45 {
46 return firstPtr;
47 }
48 firstPtr = firstPtr->next;
49 secondPtr = secondPtr->next;
50 }
51 return NULL;
52 }
